ExtendedSource checked

BNDM

BNDM addresses exact string matching by matching backward with a nondeterministic automaton encoded as bit masks.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Pattern Matching
Difficulty: Intermediate
Family: Bit-Parallel String Matching
Tier: Extended
Status: Verified
Review: Source Checked
Sources: 2
Formulas: 0
Relationships: 6
Code example: Ready
Visualization: Ready
Aliases: Backward Nondeterministic DAWG Matching

Overview

BNDM is a bit-parallel string matching method for exact string matching. It works by matching backward with a nondeterministic automaton encoded as bit masks.

Core Concepts

exact string matchingbit-parallel string matchingmatchingbit maskspattern matching

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n)

Average

O(n + m)

Worst

O(n + m)

Space

O(n + m)

When to Use

Use BNDM when solving exact string matching and you want to benefit from matching backward with a nondeterministic automaton encoded as bit masks.
Choose it when O(n + m) average/worst-case time and O(n + m) memory match your workload profile.
Prefer it over Bit-Parallel Levenshtein or Shift-And Algorithm when the problem structure favors exact string matching.

When Not to Use

Avoid when preprocessing cost is larger than the savings for a one-off tiny input.
Avoid when the alphabet or scoring assumptions do not match the sequence data.

What It Does

Computes exact string matching within Bit-Parallel String Matching workloads (O(n + m) time, O(n + m) space).
Works by matching backward with a nondeterministic automaton encoded as bit masks.
Maintains key invariants across exact string matching, bit-parallel string matching, matching.

Use Cases

Production and research workloads requiring exact string matching via matching backward with a nondeterministic automaton encoded as bit masks.
Bit-Parallel String Matching pipelines where O(n + m) time and O(n + m) space fit system constraints.
Engineering comparisons against Bit-Parallel Levenshtein and Shift-And Algorithm when tuning exact string matching.

Inputs

Text or sequence
Pattern, index, or comparison sequence

Outputs

Matches, alignment, index, or similarity value

Pseudocode

1.Preprocess the input alphabet, pattern/grammar rules, or symbol frequency tables for BNDM.
2.Construct the lookup automaton, suffix/shift index, or coding state (exact string matching, bit-parallel string matching).
3.Scan the input sequence by matching backward with a nondeterministic automaton encoded as bit masks.
4.Emit matches, derivation nodes, or encoded tokens while advancing the state transition table.
5.Finalize trailing state and return the completed exact string matching output.

Canonical Example

Input: Text or sequence configured for a representative exact string matching test case
Output: Matches, alignment, index, or similarity value satisfying BNDM invariants
Explanation: BNDM processes the input by matching backward with a nondeterministic automaton encoded as bit masks, tracking exact string matching and bit-parallel string matching to produce the verified exact string matching result.

Implementation Notes

Keep preprocessing output inspectable with short examples.
Test repeated characters and overlapping matches.
Document sentinel or alphabet assumptions.

Common Pitfalls

Mishandling empty patterns, repeated characters, or sentinel symbols.
Confusing preprocessing indexes with the query algorithm.
Forgetting whether indexing is zero-based or one-based.

Interactive Mechanism Walkthrough

Sequence Window & Automaton Alignment

Show matching backward with a nondeterministic automaton encoded as bit masks on a small exact string matching example.

Input:ABABABCABAB

Window:ABAB

Step 1 of 5: Preprocess the input alphabet, pattern/grammar rules, or symbol frequency tables for BNDM.

pattern-matching-mechanism

Notes

BNDM operates in O(n + m) time and O(n + m) space within the Bit-Parallel String Matching family. Often compared with Bit-Parallel Levenshtein and Shift-And Algorithm.