1.

Introduction to Pattern Matching

1.1 Problem Definition

String pattern matching is one of the most fundamental problems in computer science. Given a text T of
length n and a pattern P of length m (with m ≤ n), the objective is to find all occurrences — or the first
occurrence — of P within T. Formally, we seek every index i such that T[i .. i+m-1] = P[0 .. m-1].

Although the problem statement is simple, the way an algorithm exploits the structure of the pattern (or
the text) during the search has a dramatic effect on performance. This document examines four related
ideas: the general notion of pattern matching, the straightforward Naive algorithm, the linear-time
Knuth-Morris-Pratt (KMP) algorithm, and the practically fast Boyer-Moore algorithm. Each is
presented with its underlying intuition, pseudocode, a fully worked example, and a complexity analysis.

1.2 Applications
● Text editors and IDEs — implementing "find" and "find and replace" features.
● Search engines — locating keywords within indexed documents.
● Bioinformatics — locating gene or protein sub-sequences within DNA/RNA strings.
● Intrusion detection systems — matching packet payloads against known attack signatures.
● Plagiarism detection — identifying copied substrings across large corpora.
● Spam filtering and virus scanning — scanning for known malicious byte sequences.

1.3 Notation Used in This Document

Symbol Meaning

T The text string being searched, of length n

P The pattern string being searched for, of length m

n Length of the text T

m Length of the pattern P

Σ The alphabet from which characters of T and P are drawn

i Index into the text T

j Index into the pattern P

Throughout the examples, indices are zero-based (the first character of a string is at position 0), which
matches the convention used in the pseudocode listings.

String Pattern Matching Algorithms

 2. The Naive (Brute-Force) Algorithm

2.1 Concept and Intuition

The Naive algorithm, also called the Brute-Force algorithm, is the most direct approach to pattern
matching. It slides the pattern P over the text T one position at a time. At each position i, it compares P
character-by-character against the corresponding window of T. If all m characters match, an occurrence
is reported at position i. If a mismatch occurs at any point, the comparison stops, the window slides one
position to the right, and the process restarts from the beginning of the pattern.

The defining weakness of this approach is that it discards all information gained from a failed
comparison. Even if the first ten characters matched before a mismatch on the eleventh, the algorithm
does not use that knowledge — it simply shifts by one and starts over.

2.2 Pseudocode

NAIVE-SEARCH(T, P)
n = length(T)
m = length(P)
for i = 0 to n - m
j = 0
while j < m and T[i + j] == P[j]
j = j + 1
if j == m
report match at index i
// total comparisons in the worst case: O((n - m + 1) * m)

2.3 Worked Example

Let T = "ABABDABACDABABCABAB" (n = 20) and P = "ABABCABAB" (m = 9). The table below traces the
shifts the Naive algorithm attempts and where each comparison fails.

Shift i Text window Pattern Result

0 ABABD ABABC mismatch at j = 4 (D ≠ C)

1 BABDA ABABC mismatch at j = 0 (B ≠ A)

2 ABDAB ABABC mismatch at j = 2 (D ≠ A)

3 BDABA ABABC mismatch at j = 0 (B ≠ A)

4 DABAC ABABC mismatch at j = 0 (D ≠ A)

5 ABACD ABABC mismatch at j = 3 (C ≠ B)

... ... ... shifts continue one at a time

String Pattern Matching Algorithms

 10 ABABCABAB ABABCABAB full match — occurrence at index 10

Trace of the Naive algorithm searching for "ABABCABAB" in "ABABDABACDABABCABAB".

Notice that at shift 0, four characters (A, B, A, B) matched before the mismatch — yet at shift 1 the
algorithm re-compares from scratch instead of reusing that partial information. This redundant
re-checking is precisely what KMP eliminates.

2.4 Complexity Analysis

Case Time Complexity Explanation

Best case O(n) Mismatches occur immediately (at j = 0) for almost every shift.

Average case O(n) For random text over a reasonably sized alphabet, expected comparisons per shi

Worst case O(n × m) Highly repetitive strings (e.g. T = "AAAA...A", P = "AAAA...B") force nearly m com

Space complexity is O(1), since the algorithm needs no auxiliary data structures beyond loop counters.

2.5 Strengths and Weaknesses

● Strength: Extremely simple to implement and understand; no preprocessing step required.
● Strength: Performs well in practice on typical, non-repetitive text.
● Weakness: Degrades to quadratic time O(n×m) on repetitive or adversarial inputs.
● Weakness: Discards useful information from partial matches, leading to redundant comparisons.

String Pattern Matching Algorithms

 3. The Knuth-Morris-Pratt (KMP) Algorithm

3.1 Concept and Intuition

The KMP algorithm, developed by Donald Knuth, Vaughan Pratt, and James Morris, improves on the
Naive approach by never re-examining a text character that has already been matched. Its key insight is
that when a mismatch occurs after several characters have already matched, the pattern itself contains
enough information to determine how far it can safely shift without skipping any possible match. This
information is precomputed into an array called the failure function (also called the prefix function or
the partial match table).

Intuitively, the failure function records, for every prefix of the pattern, the length of the longest proper
prefix of that prefix which is also a suffix of it. When a mismatch happens at pattern position j, the
algorithm does not restart j at 0; instead it jumps to j = failure[j-1], effectively reusing the matched
characters as the new starting alignment.

3.2 The Failure Function (Prefix Table)

For a pattern P of length m, the failure function π is an array of length m where π[j] is the length of the
longest proper prefix of P[0..j] that is also a suffix of P[0..j]. Consider P = "ABABCABAB":

j 0 1 2 3 4 5 6 7 8

P[j] A B A B C A B A B

π[j] 0 0 1 2 0 1 2 3 4

Failure function (prefix table) for pattern "ABABCABAB".

For example, π[7] = 3 because the prefix P[0..7] = "ABABCABA" has "ABA" as both a prefix and a suffix,
and no longer matching segment exists.

Computing the Failure Function

COMPUTE-FAILURE(P)
m = length(P)
pi = array of size m, initialized to 0
k = 0 // length of previous longest prefix-suffix
for q = 1 to m - 1
while k > 0 and P[k] != P[q]
k = pi[k - 1]
if P[k] == P[q]
k = k + 1
pi[q] = k
return pi

String Pattern Matching Algorithms

 3.3 Pseudocode

KMP-SEARCH(T, P)
n = length(T)
m = length(P)
pi = COMPUTE-FAILURE(P)
q = 0 // number of characters currently matched
for i = 0 to n - 1
while q > 0 and P[q] != T[i]
q = pi[q - 1]
if P[q] == T[i]
q = q + 1
if q == m
report match at index (i - m + 1)
q = pi[q - 1]

Notice the crucial difference from the Naive algorithm: the outer loop iterates over the text exactly once (i
runs from 0 to n-1) and the text index i is never decremented. All backtracking happens on the pattern
index q, which is bounded by the failure function.

String Pattern Matching Algorithms

 3.4 Worked Example
Using the same strings as before — T = "ABABDABACDABABCABAB" and P = "ABABCABAB" — the
table below traces KMP's single pass over the text.

Text index i T[i] q transition Action

0 A 0→1 match, q=1

1 B 1→2 match, q=2

2 A 2→3 match, q=3

3 B 3→4 match, q=4

4 D 4→0 mismatch; q falls back via π[3]=2, then π[1]=0

5 A 0→1 match, q=1

6 B 1→2 match, q=2

7 A 2→3 match, q=3

8 C 3→0 mismatch; q falls back via π[2]=1, then π[0]=0

... ... ... matching continues without re-reading earlier text

18 B 8→9 q reaches m=9 → match reported at index 10

Trace of KMP search: each text character is read exactly once.

The critical contrast with the Naive trace in Section 2.3 is that the text pointer i advances monotonically
— it is never revisited. When the mismatch at i = 4 occurs (D vs. the expected C), KMP does not restart
comparison at text index 1 as the Naive algorithm did; instead it uses π to realign the pattern instantly and
resumes at i = 5, having never re-read T[0..3].

3.5 Complexity Analysis

Phase Time Complexity Explanation

Preprocessing (failure function)

O(m) Each pattern index is visited a bounded number of times due to the amo

Searching phase O(n) The text index i advances exactly n times; the pattern index q can only d

Overall O(n + m) Linear in the combined size of text and pattern, in every case — best, av

Space complexity is O(m), required to store the failure function array.

3.6 Strengths and Weaknesses

● Strength: Guaranteed O(n + m) time, even in the worst case — no quadratic blow-up on repetitive
input.

String Pattern Matching Algorithms

 ● Strength: Never re-reads a text character, which is valuable for streamed input.
● Weakness: Requires O(m) preprocessing and extra memory for the failure function.
● Weakness: More complex to implement correctly compared to the Naive algorithm.
● Weakness: On typical non-adversarial text, its practical speed is often similar to (and sometimes
slower than) simpler algorithms with good average-case behavior.

String Pattern Matching Algorithms

 4. The Boyer-Moore Algorithm

4.1 Concept and Intuition

The Boyer-Moore algorithm, developed by Robert Boyer and J Strother Moore, takes a fundamentally
different approach: it compares the pattern against the text from right to left, and it uses the information
from a mismatch to skip over large portions of the text — often more than one character at a time. In
practice, Boyer-Moore is one of the fastest general-purpose string matching algorithms, frequently
running in sub-linear time (examining fewer than n characters of the text) because it does not need to
inspect every character.

Boyer-Moore relies on two independent heuristics to determine how far to shift the pattern after a
mismatch: the bad character heuristic and the good suffix heuristic. At each step, the algorithm
computes the shift suggested by each heuristic and takes the larger (safer) of the two, guaranteeing
correctness while maximizing the skip distance.

4.2 Bad Character Heuristic

When a mismatch occurs between text character T[i] and pattern character P[j], the bad character rule
looks at the mismatched text character T[i] (the “bad character”) and finds its rightmost occurrence in the
pattern to the left of position j. The pattern is then shifted so that this occurrence aligns with T[i]. If the
character does not appear in the pattern at all, the pattern can be shifted entirely past the mismatch
point.

BAD-CHARACTER-TABLE(P, alphabet)
m = length(P)
for each character c in alphabet
last[c] = -1 // not present
for j = 0 to m - 1
last[P[j]] = j // record rightmost occurrence
return last

// Shift suggested on mismatch at pattern index j, text char T[i]:

// shift = max(1, j - last[T[i]])

For pattern P = "ABABCABAB", the last-occurrence table is:

Character A B C other

last index 7 8 4 -1 (not found)

Bad character table (rightmost occurrence of each character in P).

String Pattern Matching Algorithms

 4.3 Good Suffix Heuristic
The good suffix rule is used when part of the pattern has already matched (a “good suffix”) before a
mismatch occurs further to the left. It asks: does this matched suffix occur elsewhere in the pattern
(possibly preceded by a different character than the one that caused the mismatch)? If so, the pattern is
shifted to align that other occurrence with the matched text. If the suffix does not reoccur, the algorithm
checks whether a prefix of the pattern matches a suffix of the matched portion, and shifts accordingly. If
neither applies, the pattern is shifted entirely past the matched region.

● Case 1 — suffix reoccurs: shift so the next occurrence of the matched suffix (preceded by a
different character) aligns with the text.

● Case 2 — partial reoccurrence: if only part of the matched suffix appears elsewhere as a prefix of
P, shift to align that prefix.

● Case 3 — no reoccurrence: shift the pattern completely beyond the current alignment (shift by m).
The good suffix rule is more intricate to implement than the bad character rule but is particularly powerful
on patterns containing repeated substrings, since it can produce much larger shifts than the bad
character rule alone.

4.4 Pseudocode

BOYER-MOORE-SEARCH(T, P)
n = length(T)
m = length(P)
last = BAD-CHARACTER-TABLE(P, alphabet)
gs = GOOD-SUFFIX-TABLE(P) // precomputed shift table
i = 0 // alignment of pattern's start in T
while i <= n - m
j = m - 1
while j >= 0 and P[j] == T[i + j]
j = j - 1
if j < 0
report match at index i
i = i + gs[0] // shift for a full match
else
bc_shift = max(1, j - last[T[i + j]])
gs_shift = gs[j]
i = i + max(bc_shift, gs_shift)

4.5 Worked Example

Consider T = "HERE IS A SIMPLE EXAMPLE" and P = "EXAMPLE" (m = 7). Boyer-Moore compares
from the rightmost character of the pattern window backward.

Alignment i Comparison Outcome Effect

String Pattern Matching Algorithms

 0 E vs H (P[6]='E', T[6]='S')
mismatch on first (rightmost)
bad-char shift → jump ahead
comparison

4 rightmost char compared

mismatch
first quickly — 'S' not shift
adjacent
by several
in P positions

... successive large

most
jumps
windows are skipped without full
sub-linear
comparison
scanning

E-L-P-M-A-X-E
17 vs EXAMPLE (reversed compare)
all 7 characters match
match reported at index 17

Simplified trace of Boyer-Moore searching for "EXAMPLE" — most alignments are eliminated after a single character
comparison, unlike Naive or KMP which examine text left to right.

The essential behavior to observe is that because comparison starts from the end of the pattern, a
mismatch on the very first (rightmost) comparison — which is common when the text character does not
appear in the pattern at all — lets Boyer-Moore skip the entire pattern length m in a single step. This is
what gives the algorithm its sub-linear behavior in practice.

String Pattern Matching Algorithms

 4.6 Complexity Analysis
Case Time Complexity Explanation

Best case O(n / m) Large alphabets and non-repetitive patterns let the bad character rule skip m po

Average case O(n) Sub-linear in practice for typical text and moderate-to-large alphabets; widely re

Worst case O(n × m) With the bad character rule alone, pathological repetitive inputs can degrade to

Preprocessing O(m + Σ) Building the bad character table costs O(m + |Σ|); building the good suffix table

Space complexity is O(m + |Σ|): O(|Σ|) for the bad character table and O(m) for the good suffix table.

4.7 Strengths and Weaknesses

● Strength: Sub-linear average-case performance — it does not need to examine every text character.
● Strength: Performs increasingly well as the alphabet grows larger (e.g. natural-language text, DNA
with modest alphabet size still benefits, but ASCII text benefits more).

● Strength: The industry-standard choice for practical text search tools (e.g. the basis for many
implementations of grep-like utilities).

● Weakness: More complex to implement correctly, especially the good suffix table.
● Weakness: Without the good suffix rule, worst-case behavior can degrade to O(n × m).
● Weakness: Preprocessing overhead is not worthwhile for very short patterns or one-off searches.

String Pattern Matching Algorithms

 5. Comparative Analysis and Conclusion

5.1 Side-by-Side Comparison

Property Naive KMP Boyer-Moore

Comparison direction Left to right Left to right Right to left

Preprocessing None — O(1) O(m) failure function O(m + Σ) bad-char & good-suffix tables

Best-case time O(n) O(n + m) O(n / m) — sub-linear

Average-case time O(n) O(n + m) O(n) — typically sub-linear in practice

Worst-case time O(n × m) O(n + m) O(n + m) with good suffix rule

Extra space O(1) O(m) O(m + Σ)

Re-reads text characters? Yes, frequently Never Never (skips instead)

Implementation complexityVery low Moderate High

Best suited for Short patterns, simple

Streaming
use cases
data, guaranteed
Largelinear
text, time
large alphabets, practical search tools

5.2 Choosing the Right Algorithm

● Use the Naive algorithm when the pattern is short, the text is small, or simplicity and low memory
overhead matter more than worst-case guarantees.

● Use KMP when a strict, guaranteed linear-time bound is required regardless of input — for example,
in streaming contexts where the text arrives incrementally and cannot be re-read.

● Use Boyer-Moore (or its common Boyer-Moore-Horspool variant) for general-purpose text searching
over large documents, especially with alphabets larger than binary, where its sub-linear average case
gives the best real-world throughput. This is why it (or close variants) underlies many production
text-search utilities.

5.3 Conclusion
All three algorithms solve the exact same problem — locating a pattern within a text — but they embody
different trade-offs between preprocessing cost, implementation complexity, and runtime guarantees.
The Naive algorithm favors simplicity at the cost of a poor worst case. KMP guarantees linear-time
performance by exploiting self-similarity within the pattern via the failure function. Boyer-Moore achieves
the best practical performance by scanning right-to-left and using both the bad character and good suffix
heuristics to skip large sections of the text entirely. Understanding the internal mechanics and complexity
trade-offs of each algorithm makes it possible to select the most appropriate tool for a given

String Pattern Matching Algorithms

 pattern-matching task, whether that task demands simplicity, guaranteed bounds, or maximum real-world
throughput.

String Pattern Matching Algorithms

 Appendix A: Complete Python Implementations

The following runnable Python implementations correspond directly to the pseudocode presented in
Sections 2 through 4. Each function returns a list of all starting indices at which the pattern occurs in the
text.

A.1 Naive Algorithm

def naive_search(text, pattern):

n, m = len(text), len(pattern)
matches = []
for i in range(n - m + 1):
j = 0
while j < m and text[i + j] == pattern[j]:
j += 1
if j == m:
[Link](i)
return matches

A.2 Knuth-Morris-Pratt Algorithm

String Pattern Matching Algorithms

 def compute_failure(pattern):
m = len(pattern)
pi = [0] * m
k = 0
for q in range(1, m):
while k > 0 and pattern[k] != pattern[q]:
k = pi[k - 1]
if pattern[k] == pattern[q]:
k += 1
pi[q] = k
return pi

def kmp_search(text, pattern):

n, m = len(text), len(pattern)
if m == 0:
return []
pi = compute_failure(pattern)
matches = []
q = 0
for i in range(n):
while q > 0 and pattern[q] != text[i]:
q = pi[q - 1]
if pattern[q] == text[i]:
q += 1
if q == m:
[Link](i - m + 1)
q = pi[q - 1]
return matches

String Pattern Matching Algorithms

 A.3 Boyer-Moore Algorithm (Bad Character Rule)
For clarity, the implementation below uses the bad character heuristic only, which is the form popularized
as the Boyer-Moore-Horspool variant. It is simpler to implement than the full good-suffix version while
retaining strong average-case performance.

def bad_character_table(pattern):
table = {}
for i, ch in enumerate(pattern):
table[ch] = i # rightmost occurrence
return table

def boyer_moore_search(text, pattern):

n, m = len(text), len(pattern)
if m == 0:
return []
last = bad_character_table(pattern)
matches = []
i = 0
while i <= n - m:
j = m - 1
while j >= 0 and pattern[j] == text[i + j]:
j -= 1
if j < 0:
[Link](i)
i += 1
else:
bad_char = text[i + j]
shift = j - [Link](bad_char, -1)
i += max(1, shift)
return matches

A.4 Usage Example

text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"

print(naive_search(text, pattern)) # [10]

print(kmp_search(text, pattern)) # [10]
print(boyer_moore_search(text, pattern)) # [10]

Appendix B: Common Implementation Pitfalls

● Off-by-one errors: The valid range of starting shifts is 0 to n - m inclusive; using a strict upper bound
of n - m - 1 silently drops the final possible alignment.

String Pattern Matching Algorithms

 ● Empty pattern handling: An empty pattern (m = 0) is a degenerate case that should either be
rejected or defined to match at every position; unguarded code can divide by zero or index out of
range.

● Incorrect failure function base case: Forgetting to initialize π[0] = 0 in KMP, or mishandling the very
first iteration of the preprocessing loop, produces an incorrect table and silent false negatives.

● Bad character table defaults: Failing to default missing characters to -1 (meaning "not present in
the pattern") in Boyer-Moore can cause negative or undersized shifts.

● Overlapping matches: All three algorithms as presented here find overlapping occurrences (e.g.
pattern "AA" in text "AAA" matches at both index 0 and 1). If only non-overlapping matches are
desired, the next search must resume after the full length of the previous match.

● Case sensitivity and encoding: Pattern matching over multi-byte encodings (e.g. UTF-8) requires
operating on decoded code points rather than raw bytes, or matches can be reported at invalid byte
boundaries.

End of document.

String Pattern Matching Algorithms