Unit 8: Pattern Matching

I. Orientation — Foundations of String Searching

Pattern matching locates occurrences of a pattern (P) within a text (T). It is fundamental to text editors, search engines, compilers, biological sequence analysis, intrusion detection, and data compression.

• Input conventions:
  • (T=T[0\ldots n-1]) is the text of length (n).
  • (P=P[0\ldots m-1]) is the pattern of length (m).
  • Both strings use an alphabet (\Sigma), such as ASCII characters or DNA symbols ({A,C,G,T}).
  • Usually (0\leq m\leq n); an empty pattern requires an application-specific convention.
• Exact matching condition: An occurrence begins at shift (s) when
  [
  T[s+j]=P[j]\quad\text{for every }0\leq j<m,
  ]
  where (0\leq s\leq n-m).
• Possible alignments: A text of length (n) contains (n-m+1) candidate starting positions for a nonempty pattern of length (m).
• Output convention: An algorithm may return the first match, every valid shift (s), or a failure value such as (-1).
• Performance measures:
  • Preprocessing time: Work performed on (P) before searching.
  • Searching time: Work performed while examining (T).
  • Space complexity: Additional memory used beyond (T) and (P).
• Central design principle: Efficient algorithms reuse information obtained from earlier comparisons instead of restarting blindly after every mismatch.

II. Algorithmic Design — Structuring an Efficient Search

A. Design of algorithms for pattern matching problems

The design problem is to reduce unnecessary character comparisons while preserving every possible valid alignment.

• Baseline search space: Candidate shifts are
  [
  s\in{0,1,\ldots,n-m},
  ]
  so an algorithm must either test or safely eliminate each shift.
• Correctness requirement: A shift may be skipped only when information from a mismatch proves that (P) cannot match there.
• Comparison direction: The order of examination determines what information becomes reusable.
  1. Left-to-right comparison: Brute force and KMP begin with (P[0]); KMP uses matched prefixes to choose the next alignment.
  2. Right-to-left comparison: Boyer–Moore begins near (P[m-1]), allowing larger jumps when a mismatching text character is absent from relevant pattern positions.
• Preprocessing trade-off: Constructing a table from (P) adds initial cost but may accelerate repeated searches.
  • KMP builds an (m)-entry prefix table in (O(m)) time.
  • Boyer–Moore constructs bad-character and good-suffix information, commonly using (O(m+|\Sigma|)) preprocessing resources.
• Overlap handling: After finding a match, the next shift must preserve overlapping occurrences. For example, pattern ANA occurs at shifts (1) and (3) in BANANA.
• Edge conditions: A complete design handles (m>n), (m=1), repeated characters such as AAAA, matches at indices (0) and (n-m), and patterns that do not occur.
• Generic framework:
  
  TEXT

    preprocess(P)
    s ← 0
    while s ≤ n − m
        compare P with T at alignment s
        if every character matches
            report s
        s ← s + a safe shift

  
  Here, (s) is the current shift; the distinguishing feature is how each method computes the safe shift.

B. Applications and limitations

Algorithm selection depends on input size, alphabet structure, preprocessing cost, and whether the pattern is reused.

• Single short search: Brute force may be preferable because it uses (O(1)) auxiliary space and has no table-construction overhead.
• Guaranteed linear search: KMP is suitable for adversarial or repetitive input because its total running time is (O(n+m)).
• Large-alphabet practical search: Boyer–Moore often performs fewer than (n) comparisons by skipping multiple text positions.
• Exactness limitation: These algorithms require character equality; approximate matching with insertions, deletions, or substitutions needs methods such as edit-distance dynamic programming.
• Representation concern: Character indexing must match the data representation; Unicode code points, encoded bytes, and user-perceived characters are not always equivalent.

III. Direct Comparison Method — Testing Every Alignment

A. Brute-force algorithm

The brute-force algorithm aligns the pattern at every candidate shift and compares characters from left to right until a mismatch or complete match occurs.

• Procedure:
  
  TEXT

    BRUTE-FORCE(T, P)
        n ← length(T)
        m ← length(P)
        for s ← 0 to n − m
            j ← 0
            while j < m and T[s + j] = P[j]
                j ← j + 1
            if j = m
                report s

  
  Here, (s) is an alignment, and (j) is the number of pattern characters matched at that alignment.
• Correctness: The outer loop examines every legal shift (0\leq s\leq n-m); reporting occurs exactly when all (m) equalities hold.
• Worst-case time:
  [
  \Theta((n-m+1)m)=O(nm).
  ]
  This occurs when many alignments match almost completely, as with (T=\texttt{AAAAAAAAAB}) and (P=\texttt{AAAAB}).
• Best-case time: If the first character mismatches at every alignment, only (n-m+1) comparisons occur, giving (\Theta(n-m+1)), usually written (O(n)).
• Space complexity: The iterative version stores only indices (s) and (j), so auxiliary space is (O(1)).
• Worked example: For (T=\texttt{ABABA}) and (P=\texttt{ABA}), comparisons succeed at (s=0), fail immediately at (s=1), and succeed at (s=2); the reported shifts are (0) and (2).

B. Applications and limitations

Brute force is valuable chiefly for simplicity and small inputs, but it wastes information after partial matches.

• Advantages: It requires no preprocessing, works over any equality-comparable alphabet, and is straightforward to verify and implement.
• Repeated work: After matching (j) characters and encountering a mismatch, it shifts by exactly one and may compare the same text characters again.
• Adversarial behavior: Repetitive prefixes, such as pattern AAAAB against long runs of A, force nearly (m) comparisons at many shifts.
• Appropriate use: It remains effective when (m) and (n) are small, matches are expected quickly, or implementation simplicity outweighs asymptotic performance.

IV. Prefix-Based Method — Avoiding Re-examination of Text

A. Knuth-Morris-Pratt algorithm

The Knuth–Morris–Pratt (KMP) algorithm uses the pattern’s prefix structure to continue after a mismatch without moving backward in the text.

• Prefix-function definition: For each position (i), (\pi[i]) is the length of the longest proper prefix of (P[0\ldots i]) that is also its suffix. “Proper” means shorter than the whole substring.
• Concrete table: For (P=\texttt{ABABAC}),
  [
  \pi=[0,0,1,2,3,0].
  ]
  At (i=4), substring ABABA has longest proper prefix-suffix ABA, whose length is (3).
• Preprocessing:
  
  TEXT

    PREFIX(P)
        π[0] ← 0
        k ← 0
        for i ← 1 to m − 1
            while k > 0 and P[k] ≠ P[i]
                k ← π[k − 1]
            if P[k] = P[i]
                k ← k + 1
            π[i] ← k
        return π

  
  Here, (i) scans the pattern and (k) records the current prefix-suffix length.
• Search procedure:
  
  TEXT

    KMP(T, P)
        π ← PREFIX(P)
        j ← 0
        for i ← 0 to n − 1
            while j > 0 and P[j] ≠ T[i]
                j ← π[j − 1]
            if P[j] = T[i]
                j ← j + 1
            if j = m
                report i − m + 1
                j ← π[m − 1]

  
  Here, (i) is the text index and (j) is the number of currently matched pattern characters.
• Safe fallback: If a mismatch follows (j) matched characters, replacing (j) by (\pi[j-1]) retains the longest suffix already known to equal a pattern prefix.
• Complexity: Prefix construction is (O(m)), searching is (O(n)), and the table occupies (O(m)) space; total time is (O(n+m)).

B. Applications and limitations

KMP provides a deterministic linear bound, especially useful for repetitive strings and streaming text.

• No text backtracking: Index (i) never decreases, so text can be processed sequentially as it arrives.
• Overlap support: Assigning (j\leftarrow\pi[m-1]) after a match preserves a valid prefix and detects overlapping occurrences.
• Strength: Inputs such as long runs of one character cannot force (O(nm)) behavior because each fallback shortens (j).
• Limitation: KMP typically advances through every text character and may be slower in practice than Boyer–Moore when large skips are available.
• Best setting: It is well suited to predictable worst-case requirements, limited alphabets, repeated structures, and streaming systems.

V. Heuristic Skipping Method — Comparing from the Right

A. Boyer-Moore algorithm

The Boyer–Moore algorithm compares the aligned pattern from right to left and uses mismatch information to shift the pattern safely by several positions.

• Bad-character rule: Let (\operatorname{last}(c)) be the greatest index at which character (c) occurs in (P), or (-1) if absent. If (T[s+j]=c\neq P[j]), shift by
  [
  d_{\text{bad}}=\max(1,\;j-\operatorname{last}(c)).
  ]
• Good-suffix rule: If suffix (P[j+1\ldots m-1]) matched before the mismatch, align another occurrence of that suffix in (P), or align its longest suffix that is also a prefix of (P).
• Combined shift: Full Boyer–Moore uses
  [
  d=\max(d{\text{bad}},d{\text{good}}),
  ]
  where both values are precomputed or derived from pattern tables.
• Bad-character version:
  
  TEXT

    s ← 0
    while s ≤ n − m
        j ← m − 1
        while j ≥ 0 and P[j] = T[s + j]
            j ← j − 1
        if j < 0
            report s
            shift safely past the match
        else
            s ← s + max(1, j − last(T[s + j]))

  
  Here, (j) moves right-to-left and last stores rightmost pattern positions.
• Worked example: With (P=\texttt{NEEDLE}), if the aligned final text character is X, then (\operatorname{last}(\texttt{X})=-1). At (j=5), the bad-character shift is (5-(-1)=6), moving past the entire alignment.
• Complexity: Preprocessing is typically (O(m+|\Sigma|)). Basic variants can degrade to (O(nm)), while carefully implemented full versions achieve linear worst-case bounds; practical performance is often sublinear in comparisons.

B. Applications and limitations

Boyer–Moore is especially effective for long patterns and alphabets in which mismatching characters frequently permit large shifts.

• Practical advantage: Right-to-left comparison may reject an alignment after inspecting only its final character and then skip (m) positions.
• Alphabet effect: Large alphabets make absent-character mismatches common; small alphabets, such as binary data, usually produce shorter shifts.
• Pattern effect: Longer, nonrepetitive patterns tend to provide more useful bad-character and good-suffix information.
• Implementation cost: Correct good-suffix preprocessing is more complex than brute force or KMP and requires additional tables.
• Reduced advantage: Short patterns and highly repetitive strings may produce shifts of only one, limiting practical gains.
• Typical use: Variants of Boyer–Moore are common in text editors, search utilities, document scanning, and other in-memory exact-search applications.