Exact Pattern Matching

The Exact-Matching Problem and Its Baseline

Given a text string $T$ of length $N$ and a pattern string $P$ of length $M$ over an alphabet $\Sigma$, the exact string matching problem seeks all starting indices $i \in [0, N - M]$ where $T[i \dots i + M - 1] = P[0 \dots M - 1]$. Occurrences may overlap contiguous windows in $T$, such as pattern $P = \text{"ANA"}$ occurring at indices $0$ and $2$ in $T = \text{"ANANA"}$. Edge cases include empty patterns $P = \text{""}$ (which match at every index $0 \dots N$), $M > N$ (yielding zero occurrences), and handling unique sentinels (e.g., '#' or `'$'$) outside $\Sigma$ to safely join strings without false boundary matches.

The naive alignment strategy slides $P$ across $T$ one position at a time, testing character equality left-to-right. In the best case (e.g., $P[0]$ never matches $T[i]$), it makes $O(N)$ character comparisons. However, on adversarial inputs containing high internal repetition, the naive algorithm exhibits $O(N \cdot M)$ worst-case time complexity because it discards all information about characters successfully matched prior to a mismatch.

Borders, Prefix Functions, and KMP

To eliminate redundant comparisons, the Knuth-Morris-Pratt (KMP) algorithm precomputes a prefix function (or $\pi$-table) on the pattern $P$. A border of a string $S$ is a proper substring that is simultaneously a proper prefix and a proper suffix of $S$. For each position $i \in [0, M-1]$, $\pi[i]$ stores the length of the longest proper border of $P[0 \dots i]$.

When a mismatch occurs at $P[j]$ against $T[i]$ during text alignment, the algorithm has already matched $P[0 \dots j-1]$ with $T[i-j \dots i-1]$. Rather than shifting $P$ by 1 and restarting comparison from $P[0]$, KMP shifts $P$ so that its longest proper border aligns with the suffix of the matched text segment. Comparison resumes directly at $P[\pi[j-1]]$ against $T[i]$, guaranteeing that text index $i$ never steps backward.

Z-Boxes and Prefix Matches

The Z-algorithm calculates an array $Z$ for a string $S$ of length $L$, where $Z[i]$ is the length of the longest common prefix (LCP) between $S$ and the suffix of $S$ starting at index $i$ (i.e., $S[i \dots i + Z[i] - 1]$). To maintain linear time complexity, the algorithm tracks the active Z-box $[L_z, R_z]$, defined as the interval with the maximum $R_z$ reached so far where $S[L_z \dots R_z]$ matches a prefix of $S$.

When computing $Z[i]$ for $i \le R_z$, we look at the corresponding prefix index $k = i - L_z$. The previously computed value $Z[k]$ provides an initial lower bound:

1. If $Z[k] < R_z - i + 1$, then $Z[i] = Z[k]$ directly (no character comparisons needed).
2. If $Z[k] \ge R_z - i + 1$, the match extends to at least $R_z$. We explicitly compare characters beyond $R_z$ and expand $R_z$ accordingly.

To search for pattern $P$ in text $T$, we construct the concatenated string $S = P + \text{'\$'} + T$, where $\text{'\$'}$ is a unique sentinel. Any index $i$ in the $T$ portion where $Z[i] = M$ represents a full match of $P$.

flowchart TD
    Start["Process index i in S"] --> Check{"i ≤ R_z ?"}
    Check -- No --> Naive["Compute Z[i] by explicit character comparisons"]
    Check -- Yes --> Mirror["Set k = i - L_z"]
    Mirror --> BoundaryCheck{"Z[k] < R_z - i + 1 ?"}
    BoundaryCheck -- Yes --> Inside["Z[i] = Z[k]
No comparisons needed"]
    BoundaryCheck -- No --> Expand["Set Z[i] = R_z - i + 1
Compare characters past R_z"]
    Naive --> UpdateR["Update Z-box L_z, R_z if i + Z[i] - 1 > R_z"]
    Expand --> UpdateR
    Inside --> Next["Advance to i + 1"]
    UpdateR --> Next

Rolling Hashes and Rabin-Karp

The Rabin-Karp algorithm treats substring character sequences as numerical values using polynomial rolling hashing. For a string $S$ with base $B$ and prime modulus $M_h$, the hash of window $S[i \dots i + M - 1]$ is:

$$H = \left( \sum_{k=0}^{M-1} S[i + k] \cdot B^{M - 1 - k} \right) \pmod{M_h}$$

Shifting the window from $S[i \dots i + M - 1]$ to $S[i + 1 \dots i + M]$ updates the hash in $O(1)$ time by stripping the outgoing high-order character and appending the incoming low-order character:

$$H_{\text{new}} = \left( (H_{\text{old}} - S[i] \cdot B^{M-1}) \cdot B + S[i + M] \right) \pmod{M_h}$$

To prevent false positives caused by hash collisions, Rabin-Karp can perform an explicit character-by-character equality check whenever $H_{\text{text}} == H_{\text{pattern}}$, or employ double hashing with two independent coprime moduli $(M_1, M_2)$ to render collisions probability negligible ($O(1 / (M_1 M_2))$).

class RabinKarpMatcher:
    def __init__(self, pattern: str, base: int = 256, modulus: int = 1_000_000_007):
        self.pattern = pattern
        self.m = len(pattern)
        self.base = base
        self.mod = modulus

        # Precompute base^(m-1) % mod for high-order character removal
        self.high_base = 1
        for _ in range(self.m - 1):
            self.high_base = (self.high_base * self.base) % self.mod

        # Compute hash of the pattern
        self.pattern_hash = self._hash(pattern)

    def _hash(self, s: str) -> int:
        h = 0
        for char in s:
            h = (h * self.base + ord(char)) % self.mod
        return h

    def search(self, text: str) -> list[int]:
        n = len(text)
        if self.m > n or self.m == 0:
            return []

        matches = []
        # Compute initial window hash
        window_hash = self._hash(text[:self.m])

        for i in range(n - self.m + 1):
            # Verify hash match
            if window_hash == self.pattern_hash:
                # Collision-aware explicit string comparison
                if text[i : i + self.m] == self.pattern:
                    matches.append(i)

            # Roll window hash to next index if not at the end
            if i < n - self.m:
                outgoing = ord(text[i])
                incoming = ord(text[i + self.m])

                # Subtract outgoing term, scale by base, add incoming term
                window_hash = (window_hash - outgoing * self.high_base) % self.mod
                window_hash = (window_hash * self.base + incoming) % self.mod
                window_hash = (window_hash + self.mod) % self.mod  # Ensure positive value

        return matches

print("Verification")
matcher = RabinKarpMatcher("AABA")
text_sample = "AABAACAADAABAABA"
print(f"Pattern occurrences at indices: {matcher.search(text_sample)}")

Boyer-Moore, Two-Way, and Bit-Parallel Search

Different matchers optimize performance by tailoring their comparison direction, preprocessing overhead, and word-level hardware operations based on pattern length and alphabet size.

• Boyer-Moore compares pattern characters from right to left ($P[M-1 \dots 0]$). On mismatch, it uses two combination heuristics—the Bad Character Rule and the Good Suffix Rule—to skip large sections of text, reaching sublinear expected time $O(N / M)$ on large alphabets.
• Two-Way Algorithm partitions $P$ into two parts $(P_1, P_2)$ based on a critical factorization, matching $P_2$ left-to-right first and then $P_1$ right-to-left. It achieves strict $O(N)$ worst-case time using $O(1)$ auxiliary space.
• Shift-And / Shift-Or are bit-parallel algorithms that represent active matching states as bitmasks within machine words ($W$ bits). They process characters in $O(N \cdot \lceil M / W \rceil)$ time, making them exceptionally fast for short patterns ($M \le 64$).