String Matching
Algorithm
What is Pattern Matching?
• Definition:
• given a text string T and a pattern string P, find the pattern inside
the text
• T: “the rain in spain stays mainly on the plain”
• P: “n th”
• Applications:
• text editors, Web search engines (e.g. Google), image analysis
String Matching Algorithm use by
google
• Inverted Index + Token Matching (Core of Google Search)
• Approximate String Matching (for spell check, suggestions)
• Google now uses BERT (Bidirectional Encoder Representations from
Transformers) for semantic search. Instead of matching exact strings,
BERT matches the meaning of a query and a document.
For ranking, Page Rank and neural ranking models (e.g., DeepRank,
RankBrain) are used.
Algorithm used by Google
• Rabin-Karp
• Boyer Moore
• Knuth-Pratt-Morris
• Fuzzy string matching
• Page Rank
Algorithm used by YouTube
• Deep Neural Networks, Collaborative Filtering
String Concepts
• Assume S is a string of size m.
• A substring S[i .. j] of S is the string fragment between indexes i and j.
• A prefix of S is a substring S[0 .. i]
• A suffix of S is a substring S[i .. m-1]
• i is any index between 0 and m-1
Examples S
a n d r e w
0 5
• Substring S[1..3] == "ndr"
• All possible prefixes of S:
• "andrew", "andre", "andr", "and", "an”, "a"
• All possible suffixes of S:
• "andrew", "ndrew", "drew", "rew", "ew", "w"
• Check each position in the text T to see if the pattern P starts in that
position
T: a n d r e w T: a n d r e w
P: r e w P: r e w
P moves 1 char at a time through T
....
The Naive String Matching
algorithm
Naïve String Matching Algorithm
• NAIVE-STRING-MATCHER (T, P)
1. n ← length [T]
2. m ← length [P]
3. for s ← 0 to n –m(6-3) =3
4. do if P [1.....m] = T [s + 1....s + m]
5. then print "Pattern occurs with shift" s
•T= a b c a b a a b c a b a c
•P= a b a a
Rabin & Karp
Algorithm
Rabin-Karp – the idea
• Compare a string's hash values, rather than the strings themselves.
• For efficiency, the hash value of the next position in the text is easily
computed from the hash value of the current position.
How Rabin-Karp works
• Let characters in both arrays T and P be digits in radix-S notation. (S
= (0,1,...,9)
• Let p be the value of the characters in P
• Choose a prime number q such 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
• (T[s+1, .., s+m] mod q) can be incrementally computed by subtracting
the high-order digit, shifting, adding the low-order bit, all in modulo q
arithmetic.
The Rabin-Karp algorithm
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.
The Rabin-Karp algorithm
How values modulo 13 are
computed
3 1 4 1 5 2
old high- new low-
order digit 7 8 order digit
14152 ((31415 – 3 · 10000) · 10 + 2 )(mod 13)
((7 – 3 · 3) · 10 + 2 )(mod 13)
8 (mod 13)
Example
3 1 4 1 5 pattern
mod 13
7 text
1 2 3 4 5 6 7 8 9 10 11 12 13 14
2 3 1 4 1 5 2 6 7 3 9 9 2 1
mod 13
1 7 8 4 5 10 11 7 9 11
valid spurious
match hit
Rabin-Karp Algorithm
• Basic structure like the naïve algorithm, but uses modular
arithmetic as described
• For each hit, i.e., for each s where ts p (mod q), verify character
by character whether s is a valid shift or a spurious hit
• In the worst case, every shift is verified
• Running time can be shown as O((n-m+1)m)
• Average-case running time is O(n+m)
Problem of Spurious Hits
• ts p (mod q) does not imply that ts=p
• Modular equivalence does not necessarily mean that two integers are
equal
• A case in which ts p (mod q) when ts ≠ p is called a spurious
hit
• Spurious Hit: When the hash value of the pattern matches
with the hash value of window of the text but the window is
not the actual pattern then it is called a spurious hit.
Summer 2024
How to calculate Modulus value using calculator
17 mod 5
1. Divide 17/5=3.4
2. Isolate the whole number:3.4-3=0.4
3. Multiply:0.4*5=2
The Knuth-Morris-Pratt
algorithm