String Matching Algorithms
Introduction
• String matching algorithms aim to find one or several occurrences of a
string within another.
• These problems find applications in text processing,
text-editing, computer security, and DNA sequence
analysis
Outline
• String Matching Algorithms
▫ Naïve string matching algorithm
▫ Rabin-Karp’s string matching algorithm
▫ Knuth-Morris-Pratt (KMP) string matching algorithm
▫ Booyer-Moore string matching algorithm
The Problem
• Given a text T and a pattern P, check whether P occurs in T
▫ eg: T = {aabbcbbcabbbcbccccabbabbccc}
▫ Find all occurrences of pattern P = bbc
• There are variations of pattern matching
▫ Finding “approximate” matchings
▫ Finding multiple patterns etc..
• The objective of string searching is to find the location of a specific text pattern
within a larger body of text (e.g., a sentence, a paragraph, a book, etc.).
• The main considerations for string searching are speed and efficiency.
String Matching
• Given a pattern P[1..m] and a text T[1..n], find all occurrences of P in
T. Both P and T belong to ∑*.
• P occurs with shift s (beginning at s+1): P[1]=T[s+1],
P[2]=T[s+2],…,P[m]=T[s+m].
• If so, call s is a valid shift, otherwise, an invalid shift.
• Note: one occurrence begins within another one: P=abab,
T=abcabababbc, P occurs at s=3 and s=5.
An example of string matching
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Naïve string matching
Running time: O((n-m+1)m)
Problem with naïve algorithm
• Problem with Naïve algorithm:
▫ Suppose p=ababc, T=cabababcd.
• T: c a b a b a b c d
• P: a …
• P: a b a b c
• P: a…
• P: ababc
• Whenever a character mismatch occurs after matching of several
characters, the comparison begins by going back in T from the
character which follows the last beginning character
Rabin-Karp – the idea
• Compare a string's hash values, rather than the strings themselves.
How Rabin-Karp works
• Let characters in both arrays T and P be digits in radix-Σ notation. (Σ =
(0,1,...,9)
• Let p be the value of the characters in P
• Choose a prime number q that fits within a computer word to speed
computations.
• Compute (p mod q)
▫ The value of p mod q is what we will be using to find all matches of the pattern
P in T.
How Rabin-Karp works (continued)
• Compute (T[s+1, .., s+m] mod q) for s = 0 .. n-m
• Test against P only those sequences in T having the same (mod q)
value
•.
A Rabin-Karp example
• Given T = 31415926535 and P = 26
• We choose q = 11
• P mod q = 26 mod 11 = 4
3 1 4 1 5 9 2 6 5 3 5
31 mod 11 = 9 not equal to 4
3 1 4 1 5 9 2 6 5 3 5
14 mod 11 = 3 not equal to 4
3 1 4 1 5 9 2 6 5 3 5
41 mod 11 = 8 not equal to 4
Rabin-Karp example continued
3 1 4 1 5 9 2 6 5 3 5
15 mod 11 = 4 equal to 4 -> spurious hit
3 1 4 1 5 9 2 6 5 3 5
59 mod 11 = 4 equal to 4 -> spurious hit
3 1 4 1 5 9 2 6 5 3 5
92 mod 11 = 4 equal to 4 -> spurious hit
3 1 4 1 5 9 2 6 5 3 5
26 mod 11 = 4 equal to 4 -> an exact match!!
3 1 4 1 5 9 2 6 5 3 5
65 mod 11 = 10 not equal to 4
Rabin-Karp example continued
3 1 4 1 5 9 2 6 5 3 5
53 mod 11 = 9 not equal to 4
3 1 4 1 5 9 2 6 5 3 5
35 mod 11 = 2 not equal to 4
As we can see, when a match is found, further testing is
done to insure that a match has indeed been found.
Analysis
• The running time of the algorithm in the worst-case scenario is bad..
But it has a good average-case running time.
• O(mn) in worst case
• O(n) if we’re more optimistic…
Knuth-Morris-Pratt (KMP) algorithm
• Idea: after some character (such as q) matches of P with T and then a
mismatch, the matched q characters allows us to determine
immediately that certain shifts are invalid. So directly go to the shift
which is potentially valid.
• The matched characters in T are in fact a prefix of P, so just from P, it is
OK to determine whether a shift is invalid or not.
• Precalculate the longest prefix which is also a suffix for each index and
store in an array.
• When ever a mismatch occurs look up the table and determine where
you should start comparing in the pattern
Steps
Create a prefix table for the given table- If we precompute prefix
function of P (against itself), then when ever a mismatch occurs, the
prefix function can determine which shift(s) are invalid and directly
ruled out. So move directly to the shift which is potentially valid.
However, there is no need to compare these characters again since
they are equal.
Initialise your text from I = 1 to n and q= 0 to m
Comparee T[i] with P[q+1], if the same then increment I and q, if
different bring q to π[q]. If 0 increment I
If q reaches to m then the pattern is found
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
20
The KMP Algorithm Algorithm KMPMatch(T, P)
F ← failureFunction(P)
• The failure function can be i←0
represented by an array and can be j←0
computed in O(m) time while i < n
if T[i] = P[j]
• At each iteration of the while-loop, if j = m − 1
there are no more than 2n return i − j { match }
iterations of the while-loop else
i←i+1
• Thus, KMP’s algorithm runs in j←j+1
optimal time O(m + n) else
if j > 0
j ← F[j − 1]
else
i←i+1
return −1 { no match }
Conclusions & Summary
• Implement in a practical programming language and collect the statistics
for efficiency/effectiveness
● Naïve string
● KMP
● Rabin -Karp