String Matching

Finding all occurrences of a pattern in

the text.
Applications
• Spell Checkers.
• Search Engines.
• Spam Filters.
• Intrusion Detection System.
• Plagiarism Detection.
• Bioinformatics – DNA Sequencing.
• Digital Forensics.
• Information Retrieval, etc.
String Matching Problem
• Let,
• Text T [1..n] is an array of length n.
• Pattern P [1..m] is an array of length m ≤ n.
• P and T are drawn from a finite alphabet Σ.
– Σ = {0,1} or Σ = {a, b, …, z}.
• Example:
–T=abcabaabcabac
–P=abaa
Contd… T 1
a
2
b
3
c
4
a
5
b
6
a
7
a
8
b
9
c
10
a
11
b
12
a
13
c
shift = 0 P a b a a
shift = 1 P a b a a
shift = 2 P a b a a
shift = 3 P a b a a
shift = 4 P a b a a
shift = 5 P a b a a
shift = 6 P a b a a
shift = 7 P a b a a
shift = 8 P a b a a
shift = 9 P a b a a
Contd…

• Shift s a valid shift, if P occurs with shift s in T.

– 0 ≤ s ≤ n – m and T [s + 1..s + m] = P [1..m].
• Otherwise, shift s is an invalid shift.
• String-matching problem means finding all valid
shifts with which a given pattern P occurs in a given
text T .
Naive String Matching Algorithm
NAIVE-STRING-MATCHER(T,P)
1. n = [Link]
2. m = [Link]
3. for s = 0 to n – m
4. if P [1..m] == T [s + 1..s + m]
5. print “Pattern occurs with shift” s

• Complexity: O((n – m + 1)m)

Example

• Text T = acaabc, and pattern P = aab.

Rabin-Karp Algorithm
• Uses elementary number-theoretic notions.
– Equivalence of two numbers modulo a third
number.
• Let, Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
• String of k consecutive characters represents a
length-k decimal number.
– Thus, character string 31415 corresponds to the
decimal number 31,415.
• Note:
– In the general case, each character is a digit in
radix-d notation, where d = |Σ|.)
Example
P 3 1 4 1 5 mod 13 = 7

T 2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1

mod 13
8
9
3
A few calculations…
• For a pattern P [1..m], let p denote its corresponding
value in radix-d notation.
• Using Horner’s rule, p can be computed in time ϴ(m).
p = P [m] + d(P [m – 1] + d(P [m – 2] + … + d(P [2] + dP[1]) …)).

• Similarly, for a text T [1..n], let ts denotes the radix-d

notation value of the length-m substring T [s + 1..s +
m], for s = 0, 1, …,n – m.
• Again, t0 can be computed from T [1..m] in ϴ(m).
Contd…
• Each of the remaining values t1, t2, …, tn – m can be
computed in constant time.
– Subtracting dm – 1T [s + 1] removes the high-order digit
from ts, multiplying the result by d shifts the number left
by one digit position, and adding T [s + m + 1] brings in
the appropriate low-order digit.
ts +1 = d (ts – dm – 1T [s + 1]) + T [s + m + 1].
• Let h = dm – 1, then
ts +1 = d (ts – hT [s + 1]) + T [s + m + 1].
• Modulus:
– p modulo q takes ϴ(m) time.
– For all ts, ts modulo q takes ϴ(n – m + 1) time.
Algorithm
Modular Arithmetic

(A * B) mod C = (A mod C * B mod C) mod C

(A + B) mod C = (A mod C + B mod C) mod C

Example – 1
Index 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Text (T) 2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1
Pattern: 3 1 4 1 5
Σ = {0, 1, …, 9} d = |Σ| = 10 q = 13
• n = 19, m = 5, n – m = 14.
• h = 105-1 mod 13 = 104 mod 13 = 3.
• p = (3 × 104 + 1 × 103 + 4 × 102 + 1 × 101 + 5 × 100) mod 13 = 7.
• t0 = (2 × 104 + 3 × 103 + 5 × 102 + 9 × 101 + 0 × 100) mod 13 = 8.

Step 1: s = 0, t0 = 8, p = 7.
p == t0 → No.
s < 14 → Yes.
ts +1 = d (ts – hT [s + 1]) + T [s + m + 1] (mod 13)
t1 = 10 (8 – 3 (2)) + 2 (mod 13)
t1 = 10 (2) + 2 (mod 13) = 22 (mod 13) = 9.
Contd…
Index 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Text (T) 2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1
Pattern: 3 1 4 1 5
Σ = {0, 1, …, 9} d = |Σ| = 10 q = 13
• n = 19, m = 5, n – m = 14.
• h = 105-1 mod 13 = 104 mod 13 = 3.
• p = (3 × 104 + 1 × 103 + 4 × 102 + 1 × 101 + 5 × 100) mod 13 = 7.
• t0 = (2 × 104 + 3 × 103 + 5 × 102 + 9 × 101 + 0 × 100) mod 13 = 8.

Step 2: s = 1, t1 = 9, p = 7.
p == t1 → No.
s < 14 → Yes.
ts +1 = d (ts – hT [s + 1]) + T [s + m + 1] (mod 13)
t2 = 10 (9 – 3 (3)) + 3 (mod 13)
t2 = 10 (0) + 3 (mod 13) = 3 (mod 13) = 3.
Contd…
Index 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Text (T) 2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1
Pattern: 3 1 4 1 5
Σ = {0, 1, …, 9} d = |Σ| = 10 q = 13
• n = 19, m = 5, n – m = 14.
• h = 105-1 mod 13 = 104 mod 13 = 3.
• p = (3 × 104 + 1 × 103 + 4 × 102 + 1 × 101 + 5 × 100) mod 13 = 7.
• t0 = (2 × 104 + 3 × 103 + 5 × 102 + 9 × 101 + 0 × 100) mod 13 = 8.

Step 3: s = 2, t2 = 3, p = 7.
p == t2 → No.
s < 14 → Yes.
ts +1 = d (ts – hT [s + 1]) + T [s + m + 1] (mod 13)
t3 = 10 (3 – 3 (5)) + 1 (mod 13) = 10 (-12) + 1 (mod 13)
Because -12 mod 13 = 1 t3 = 10 (1) + 1 (mod 13) = 11 (mod 13) = 11.
Contd…
Index 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Text (T) 2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1
Pattern: 3 1 4 1 5
Σ = {0, 1, …, 9} d = |Σ| = 10 q = 13
• n = 19, m = 5, n – m = 14.
• h = 105-1 mod 13 = 104 mod 13 = 3.
• p = (3 × 104 + 1 × 103 + 4 × 102 + 1 × 101 + 5 × 100) mod 13 = 7.
• t0 = (2 × 104 + 3 × 103 + 5 × 102 + 9 × 101 + 0 × 100) mod 13 = 8.

Step 4: s = 3, t3 = 11, p = 7.
p == t3 → No.
s < 14 → Yes.
ts +1 = d (ts – hT [s + 1]) + T [s + m + 1] (mod 13)
t4 = 10 (11 – 3 (9)) + 4 (mod 13) = 10 (-16) + 4 (mod 13)
Because -16 mod 13 = 10 t4 = 10 (10) + 4 (mod 13) = 104 (mod 13) = 0.
Contd…
Index 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Text (T) 2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1
Pattern: 3 1 4 1 5
Σ = {0, 1, …, 9} d = |Σ| = 10 q = 13
• n = 19, m = 5, n – m = 14.
• h = 105-1 mod 13 = 104 mod 13 = 3.
• p = (3 × 104 + 1 × 103 + 4 × 102 + 1 × 101 + 5 × 100) mod 13 = 7.
• t0 = (2 × 104 + 3 × 103 + 5 × 102 + 9 × 101 + 0 × 100) mod 13 = 8.

Step 5: s = 4, t4 = 0, p = 7.
p == t4 → No.
s < 14 → Yes.
ts +1 = d (ts – hT [s + 1]) + T [s + m + 1] (mod 13)
t5 = 10 (0 – 3 (0)) + 1 (mod 13)
t5 = 1 (mod 13) = 1.
Contd…
Index 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Text (T) 2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1
Pattern: 3 1 4 1 5
Σ = {0, 1, …, 9} d = |Σ| = 10 q = 13
• n = 19, m = 5, n – m = 14.
• h = 105-1 mod 13 = 104 mod 13 = 3.
• p = (3 × 104 + 1 × 103 + 4 × 102 + 1 × 101 + 5 × 100) mod 13 = 7.
• t0 = (2 × 104 + 3 × 103 + 5 × 102 + 9 × 101 + 0 × 100) mod 13 = 8.

Step 6: s = 5, t5 = 1, p = 7.
p == t5 → No.
s < 14 → Yes.
ts +1 = d (ts – hT [s + 1]) + T [s + m + 1] (mod 13)
t6 = 10 (1 – 3 (2)) + 5 (mod 13) = 10 (-5) + 5 (mod 13)
Because -5 mod 13 = 8 t6 = 10 (8) + 5 (mod 13) = 85 (mod 13) = 7.
Contd…
Index 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Text (T) 2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1
Pattern: 3 1 4 1 5
Σ = {0, 1, …, 9} d = |Σ| = 10 q = 13
• n = 19, m = 5, n – m = 14.
• h = 105-1 mod 13 = 104 mod 13 = 3.
• p = (3 × 104 + 1 × 103 + 4 × 102 + 1 × 101 + 5 × 100) mod 13 = 7.
• t0 = (2 × 104 + 3 × 103 + 5 × 102 + 9 × 101 + 0 × 100) mod 13 = 8.
Step 7: s = 6, t6 = 7, p = 7.
p == t6 → Yes.
Character by character matching p[1..5] == T[7..11].
{3 1 4 1 5} == {3 1 4 1 5}. Match, hence s = 6 is a valid shift.
s < 14 → Yes.
ts +1 = d (ts – hT [s + 1]) + T [s + m + 1] (mod 13)
t7 = 10 (7 – 3 (3)) + 2 (mod 13) = 10 (-2) + 2 (mod 13)
Because -2 mod 13 = 11
t7 = 10 (11) + 2 (mod 13) = 112 (mod 13) = 8.
Contd…
Index 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Text (T) 2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1
Pattern: 3 1 4 1 5
Σ = {0, 1, …, 9} d = |Σ| = 10 q = 13
• n = 19, m = 5, n – m = 14.
• h = 105-1 mod 13 = 104 mod 13 = 3.
• p = (3 × 104 + 1 × 103 + 4 × 102 + 1 × 101 + 5 × 100) mod 13 = 7.
• t0 = (2 × 104 + 3 × 103 + 5 × 102 + 9 × 101 + 0 × 100) mod 13 = 8.

Step 8: s = 7, t7 = 8, p = 7.
p == t7 → No.
s < 14 → Yes.
ts +1 = d (ts – hT [s + 1]) + T [s + m + 1] (mod 13)
t8 = 10 (8 – 3 (1)) + 6 (mod 13)
t8 = 10 (5) + 6 (mod 13) = 56 (mod 13) = 4.
Contd…
Index 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Text (T) 2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1
Pattern: 3 1 4 1 5
Σ = {0, 1, …, 9} d = |Σ| = 10 q = 13
• n = 19, m = 5, n – m = 14.
• h = 105-1 mod 13 = 104 mod 13 = 3.
• p = (3 × 104 + 1 × 103 + 4 × 102 + 1 × 101 + 5 × 100) mod 13 = 7.
• t0 = (2 × 104 + 3 × 103 + 5 × 102 + 9 × 101 + 0 × 100) mod 13 = 8.

Step 9: s = 8, t8 = 4, p = 7.
p == t8 → No.
s < 14 → Yes.
ts +1 = d (ts – hT [s + 1]) + T [s + m + 1] (mod 13)
t9 = 10 (4 – 3 (4)) + 7 (mod 13) = 10 (-8) + 7 (mod 13)
Because -8 mod 13 = 5 t9 = 10 (5) + 7 (mod 13) = 57 (mod 13) = 5.
Contd…
Index 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Text (T) 2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1
Pattern: 3 1 4 1 5
Σ = {0, 1, …, 9} d = |Σ| = 10 q = 13
• n = 19, m = 5, n – m = 14.
• h = 105-1 mod 13 = 104 mod 13 = 3.
• p = (3 × 104 + 1 × 103 + 4 × 102 + 1 × 101 + 5 × 100) mod 13 = 7.
• t0 = (2 × 104 + 3 × 103 + 5 × 102 + 9 × 101 + 0 × 100) mod 13 = 8.

Step 10: s = 9, t9 = 5, p = 7.
p == t9 → No.
s < 14 → Yes.
ts +1 = d (ts – hT [s + 1]) + T [s + m + 1] (mod 13)
t10 = 10 (5 – 3 (1)) + 3 (mod 13)
t10 = 10 (2) + 3 (mod 13) = 23 (mod 13) = 10.
Contd…
Index 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Text (T) 2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1
Pattern: 3 1 4 1 5
Σ = {0, 1, …, 9} d = |Σ| = 10 q = 13
• n = 19, m = 5, n – m = 14.
• h = 105-1 mod 13 = 104 mod 13 = 3.
• p = (3 × 104 + 1 × 103 + 4 × 102 + 1 × 101 + 5 × 100) mod 13 = 7.
• t0 = (2 × 104 + 3 × 103 + 5 × 102 + 9 × 101 + 0 × 100) mod 13 = 8.

Step 11: s = 10, t10 = 10, p = 7.

p == t10 → No.
s < 14 → Yes.
ts +1 = d (ts – hT [s + 1]) + T [s + m + 1] (mod 13)
t11 = 10 (10 – 3 (5)) + 9 (mod 13) = 10 (-5) + 9 (mod 13)
Because -5 mod 13 = 8 t11 = 10 (8) + 9 (mod 13) = 89 (mod 13) = 11.
Contd…
Index 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Text (T) 2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1
Pattern: 3 1 4 1 5
Σ = {0, 1, …, 9} d = |Σ| = 10 q = 13
• n = 19, m = 5, n – m = 14.
• h = 105-1 mod 13 = 104 mod 13 = 3.
• p = (3 × 104 + 1 × 103 + 4 × 102 + 1 × 101 + 5 × 100) mod 13 = 7.
• t0 = (2 × 104 + 3 × 103 + 5 × 102 + 9 × 101 + 0 × 100) mod 13 = 8.

Step 12: s = 11, t11 = 11, p = 7.

p == t11 → No.
s < 14 → Yes.
ts +1 = d (ts – hT [s + 1]) + T [s + m + 1] (mod 13)
t12 = 10 (11 – 3 (2)) + 9 (mod 13)
t12 = 10 (5) + 9 (mod 13) = 59 (mod 13) = 7.
Contd…
Index 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Text (T) 2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1
Pattern: 3 1 4 1 5
Σ = {0, 1, …, 9} d = |Σ| = 10 q = 13
• n = 19, m = 5, n – m = 14.
• h = 105-1 mod 13 = 104 mod 13 = 3.
• p = (3 × 104 + 1 × 103 + 4 × 102 + 1 × 101 + 5 × 100) mod 13 = 7.
• t0 = (2 × 104 + 3 × 103 + 5 × 102 + 9 × 101 + 0 × 100) mod 13 = 8.
Step 13: s = 12, t12 = 7, p = 7.
p == t12 → Yes.
Character by character matching p[1..5] == T[13..17].
{3 1 4 1 5} == {6 7 3 9 9}. Mismatch occurs at first character.
s < 14 → Yes.
ts +1 = d (ts – hT [s + 1]) + T [s + m + 1] (mod 13)
t13 = 10 (7 – 3 (6)) + 2 (mod 13) = 10 (-11) + 2 (mod 13)
Because -11 mod 13 = 2 t
13 = 10 (2) + 2 (mod 13) = 22 (mod 13) = 9.
Contd…
Index 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Text (T) 2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1
Pattern: 3 1 4 1 5
Σ = {0, 1, …, 9} d = |Σ| = 10 q = 13
• n = 19, m = 5, n – m = 14.
• h = 105-1 mod 13 = 104 mod 13 = 3.
• p = (3 × 104 + 1 × 103 + 4 × 102 + 1 × 101 + 5 × 100) mod 13 = 7.
• t0 = (2 × 104 + 3 × 103 + 5 × 102 + 9 × 101 + 0 × 100) mod 13 = 8.

Step 14: s = 13, t13 = 9, p = 7.

p == t13 → No.
s < 14 → Yes.
ts +1 = d (ts – hT [s + 1]) + T [s + m + 1] (mod 13)
t14 = 10 (9 – 3 (7)) + 1 (mod 13) = 10 (-12) + 1 (mod 13)
Because -12 mod 13 = 1 t14 = 10 (1) + 1 (mod 13) = 11 (mod 13) = 11.
Contd…
Index 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Text (T) 2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1
Pattern: 3 1 4 1 5
Σ = {0, 1, …, 9} d = |Σ| = 10 q = 13
• n = 19, m = 5, n – m = 14.
• h = 105-1 mod 13 = 104 mod 13 = 3.
• p = (3 × 104 + 1 × 103 + 4 × 102 + 1 × 101 + 5 × 100) mod 13 = 7.
• t0 = (2 × 104 + 3 × 103 + 5 × 102 + 9 × 101 + 0 × 100) mod 13 = 8.

Step 15: s = 14, t14 = 11, p = 7.

p == t14 → No.
s < 14 → No.

Step 16: s = 15.

Loop terminates.
 Index
Example – 2 Text (T)
1

a
2

a
3

b
4

b
5

c
6

a b
7 8

a
ASCII 97 97 98 98 99 97 98 97
• n = 8, m = 3, n – m = 5. Pattern: c a b
• h = 263-1 mod 3
= 262 mod 3 = 1.
Σ = {a, b, …, z} d = |Σ| = 26 q=3
• p = (99 × 262 + 97 × 261 + 98 × 260) mod 3 = 1.
• t0 = (97 × 262 + 97 × 261 + 98 × 260) mod 3 = 2.

Step 1: s = 0, t0 = 2, p = 1.
p == t0 → No.
s < 5 → Yes.
ts +1 = d (ts – hT [s + 1]) + T [s + m + 1] (mod 3)
t1 = 26 (2 – 1 (97)) + 98 (mod 3)
t1 = 26 (2 – 1 (1)) + 2 (mod 3)
(because 97 mod 3 = 1 and 98 mod 3 = 2)
= 26 (1) + 2 (mod 3)
= 28 (mod 3) = 1.
 Index
Contd… Text (T)
1

a
2

a
3

b
4

b
5

c
6

a
7

b
8

a
ASCII 97 97 98 98 99 97 98 97

Pattern: c a b

Step 2: s = 1, t1 = 1, p = 1.
p == t1 → Yes.
Character by character matching p[1..3] == T[2..4].
{c a b} == {a b b}. Mismatch occurs at first character.
s < 5 → Yes.
ts + 1 = d (ts – hT [s + 1]) + T [s + m + 1] (mod 3)
t2 = 26 (1 – 1 (97)) + 99 (mod 3)
t2 = 26 (1 – 1 (1)) + 0 (mod 3)
(because 97 mod 3 = 1 and 99 mod 3 = 0)
= 26 (0) (mod 3)
= 0.
 Index
Contd… Text (T)
1

a
2

a
3

b
4

b
5

c
6

a
7

b
8

a
ASCII 97 97 98 98 99 97 98 97

Pattern: c a b

Step 3: s = 2, t2 = 0, p = 1.
p == t2 → No.
s < 5 → Yes.
ts + 1 = d (ts – hT [s + 1]) + T [s + m + 1] (mod 3)
t3 = 26 (0 – 1 (98)) + 97 (mod 3)
t3 = 26 (0 – 1 (2)) + 1 (mod 3)
(because 97 mod 3 = 1 and 98 mod 3 = 2)
= 26 (0 – 2) + 1 (mod 3)
= 26 (0 + 1) + 1 (mod 3)
(because 3's complement of -2 = 1)
= 26 (1) + 1 (mod 3) = 27 (mod 3) = 0.
 Index
Contd… Text (T)
1

a
2

a
3

b
4

b
5

c
6

a
7

b
8

a
ASCII 97 97 98 98 99 97 98 97

Pattern: c a b

Step 4: s = 3, t3 = 0, p = 1.
p == t3 → No.
s < 5 → Yes.
ts + 1 = d (ts – hT [s + 1]) + T [s + m + 1] (mod 3)
t4 = 26 (0 – 1 (98)) + 98 (mod 3)
t4 = 26 (0 – 1 (2)) + 2 (mod 3)
(because 98 mod 3 = 2)
= 26 (0 – 2) + 2 (mod 3)
= 26 (0 + 1) + 2 (mod 3)
(because 3's complement of -2 = 1)
= 26 (1) + 2 (mod 3) = 28 (mod 3) = 1.
 Index
Contd… Text (T)
1

a
2

a
3

b
4

b
5

c
6

a
7

b
8

a
ASCII 97 97 98 98 99 97 98 97

Pattern: c a b

Step 5: s = 4, t4 = 1, p = 1.
p == t4 → Yes.
Character by character matching p[1..3] == T[5..7].
{c a b} == {c a b}. Match, hence s = 4 is a valid shift.
s < 5 → Yes.
ts + 1 = d (ts – hT [s + 1]) + T [s + m + 1] (mod 3)
t5 = 26 (1 – 1 (99)) + 97 (mod 3)
t5 = 26 (1 – 1 (0)) + 1 (mod 3)
(because 97 mod 3 = 1 and 99 mod 3 = 0)
= 26 (1 – 0) + 1 (mod 3)
= 26 (1) + 1 (mod 3) = 27 (mod 3) = 0.
 Index
Contd… Text (T)
1

a
2

a
3

b
4

b
5

c
6

a
7

b
8

a
ASCII 97 97 98 98 99 97 98 97

Pattern: c a b

Step 6: s = 5, t5 = 0, p = 1.
p == t5 → No.
s < 5 → No.

Step 7: s = 6.
Loop terminates.

Text (T) a a b b c a b a

2 1 0 0 1 0
Complexity
• Takes ϴ(m) preprocessing time.
• Worst-case running time is O(m (n – m + 1)).
– Example: P = am and T = an, each of the [n – m +
1] possible shifts is valid.
• In many applications, there are a few valid shifts
(say some constant c). In such applications, the
expected matching time is only O(n – m + 1) + cm),
plus the time required to process spurious hits.
Contd…
• Probabilistic analysis
– The probability of a false positive hit for a random
input is 1/q.
– The expected number of false positive hits is O(n/q).
– The expected run time is O(n) + O(m(v + n/q))), if v is
the number of valid shifts.
• Choosing q ≥ m and having only a constant number of
hits, then the expected matching time is O(n + m).
• Since m ≤ n, this expected matching time is O(n).
Knuth-Morris-Pratt Algorithm
• Based on the concept of prefix function for a
pattern.
– Encapsulates knowledge about how the pattern
matches against shifts of itself.
– This information can be used to avoid testing of
invalid shifts.
• T: b a c b a b a b a a b c b a b
• P: ababaca
Contd…
Prefix Function
q 1 2 3 4 5 6 7
• P: a b a b a c a k 0 0 1 2
• Pq = P[1..q]
• P1 = {a}. Pk = {}. No matching prefix and suffix of P1.
• P2 = {a b}. Pk = {}. No matching prefix and suffix of P2.
• P3 = {a b a}. Pk = {a}. P4 = {a b a b}. Pk = {a b}.
Prefix Suffix k Prefix Suffix k
a a 1 a b 1
ab ba 2 ab ab 2
aba bab 3
Contd… q 1 2 3 4 5 6 7
k 0 0 1 2 3 0 1
• P: a b a b a c a
• Pq = P[1..q]
• P5 = {a b a b a}. Pk = {a b a}. • P7 = {a b a b a c a}. Pk = {a}.
Keep the longest. Prefix Suffix k
Prefix Suffix k a a 1
a a 1 ab ca 2
ab ba 2 aba aca 3
aba aba 3 abab baca 4
abab baba 4 ababa abaca 5
ababac babaca 6
• P6 = {a b a b a c}. Pk = {}. No matching prefix and suffix of P6 as 'c'
does not appear in any of the proper prefix.
Prefix Function
q→

k→

• Given a pattern P [1..m], the prefix function for the

pattern P is the function Π : {1, 2, …, m} → {0, 1,
…, m – 1} such that
Π [q] = max {k : k < q and Pk is a proper suffix of Pq.
• It contains the length of the longest prefix of P that
is a proper suffix of Pq.
Contd…
Example(Preprocessing)

P[i] a b a b a c a

∏[i]
m = 7, ∏[1] = 0, k = 0.
q k P[k+1] P[q] Processing
KMP Algorithm
Complexity
• The COMPUTE-PREFIXFUNCTION runs in ϴ(m) time as the while
loop in lines 6–7 executes at most m – 1 times altogether.
1. Line 4 starts k at 0, and the only way to increase k is the increment
operation in line 9, which executes at most once per iteration of the
for loop of lines 5–10. Thus, the total increase in k is at most m – 1.
2. Second, since k < q upon entering the for loop and each iteration of
the loop increments q and k < q always. Assignments in lines 3 and 10
ensure that Π[q] < q for all q = 1, 2, …, m, which means that each
iteration of the while loop decreases k.
3. Third, k never becomes negative.
– Altogether, the total decrease in k from the while loop is bounded
from above by the total increase in k over all iterations of the for loop,
which is m – 1.
• Using similar analysis, the matching time of KMP-MATCHER is
ϴ(n).
Example (KMP) n = 15
m=7
T[i] b a c b a b a b a b a c a a b

i q T[i] P[q+1] Processing

1 0 b a q>0 ×, b==a ×, q=0≠7

2 0 a a q>0 ×, a==a √, q=1≠7

3 1 c b q>0 √, c≠b √, q=∏[1]=0

0 c a q>0 ×, c==a ×, q=0≠7

4 0 b a q>0 ×, b==a ×, q=0≠7

5 0 a a q>0 √, a==a √, q=1≠7

6 1 b b q>0 √, b==b √, q=2≠7

7 2 a a q>0 √, a==a √, q=3≠7

8 3 b b q>0 √, b==b √, q=4≠7

Example (KMP) n = 15
m=7
T[i] b a c b a b a b a b a c a a b
i q T[i] P[q+1] Processing
9 4 a a q>0 √, a==a √, q=5≠7
10 5 b c q>0 √, b≠c √, q=∏[5]=3
3 b b q>0 √, b==b √, q=4≠7
11 4 a a q>0 √, a==a √, q=5≠7
12 5 c c q>0 √, c==c √, q=6≠7
13 6 a a q>0 √, a==a √, q=7==7
Shift 13-7=6, q=∏[7]=1
14 1 a b q>0 √, a≠b √, q=∏[1]=0
0 a a q>0 ×, a==a √, q=1≠7
15 1 b b q>0 √, b==b √, q=2≠7
16 Stop
Detailed Example (Preprocessing)

• m = 7, Π[1] = 0, k = 0.
Step 1: q = 2, k = 0 P[k + 1] == P[q]
(if) P[1] == P[2]. Mismatch.
Π[2] = 0.
Step 2: q = 3, k = 0. P[k + 1] == P[q]
(if) P[1] == P[3]. Match. k++ = 1
Π[3] = 1.
Step 3: q = 4, k = 1. P[k + 1] == P[q]
(if) P[2] == P[4]. Match. k++ = 2
Π[4] = 2.
Contd…
Step 4: q = 5, k = 2 P[k + 1] == P[q]
(if) P[3] == P[5]. Match. k++ = 3
Π[5] = 3.
Step 5: q = 6, k = 3. P[k + 1] == P[q]
(while) P[4] == P[6]. Mismatch. k = Π[k] = 1
(while) P[2] == P[6]. Mismatch. k = Π[k] = 0
(if) P[1] == P[6]. Mismatch.
Π[6] = 0.
Step 6: q = 7, k = 0. P[k + 1] == P[q]
(if) P[1] == P[7]. Match. k++ = 1
Π[7] = 1.
Step 7: q=8 Loop terminates.
Contd… n = 15
m=7
(Matching)
• T: b a c b a b a b a b a c a a b

• P: a b a b a c a

Step 1: i = 1, q = 0 P[q + 1] == T[i]

(if) P[1] == T[1]. Mismatch.
b a c b a b a b a b a c a a b

a b a b a c a
Contd… n = 15
m=7

Step 2: i = 2, q = 0 P[q + 1] == T[i]

(if) P[1] == T[2]. Match. q++ = 1

b a c b a b a b a b a c a a b

a b a b a c a
Contd… n = 15
m=7

Step 3: i = 3, q = 1 P[q + 1] == T[i]

(while) P[2] == T[3]. Mismatch.
q = Π[q] = 0
b a c b a b a b a b a c a a b

a b a b a c a

(if) P[1] == T[3]. Mismatch.

b a c b a b a b a b a c a a b

a b a b a c a
Contd… n = 15
m=7

Step 4: i = 4, q = 0 P[q + 1] == T[i]

(if) P[1] == T[4]. Mismatch.

b a c b a b a b a b a c a a b

a b a b a c a
Contd… n = 15
m=7

Step 5: i = 5, q = 0 P[q + 1] == T[i]

(if) P[1] == T[5]. Match. q++ = 1

b a c b a b a b a b a c a a b

a b a b a c a
Contd… n = 15
m=7

Step 6: i = 6, q = 1 P[q + 1] == T[i]

(if) P[2] == T[6]. Match. q++ = 2

b a c b a b a b a b a c a a b

a b a b a c a
Contd… n = 15
m=7

Step 7: i = 7, q = 2 P[q + 1] == T[i]

(if) P[3] == T[7]. Match. q++ = 3

b a c b a b a b a b a c a a b

a b a b a c a
Contd… n = 15
m=7

Step 8: i = 8, q = 3 P[q + 1] == T[i]

(if) P[4] == T[8]. Match. q++ = 4

b a c b a b a b a b a c a a b

a b a b a c a
Contd… n = 15
m=7

Step 9: i = 9, q = 4 P[q + 1] == T[i]

(if) P[5] == T[9]. Match. q++ = 5

b a c b a b a b a b a c a a b

a b a b a c a
Contd… n = 15
m=7

Step 10: i = 10, q = 5 P[q + 1] == T[i]

(while) P[6] == T[10]. Mismatch. q = Π[q] = 3
b a c b a b a b a b a c a a b

a b a b a c a
(if) P[4] == T[10]. Match. q++ = 4
b a c b a b a b a b a c a a b
Shifts skipped = 1 and first three
characters are not compared.
a b a b a c a
Comparison starts from P[4].
Contd… n = 15
m=7

Step 11: i = 11, q = 4 P[q + 1] == T[i]

(if) P[5] == T[11]. Match. q++ = 5

b a c b a b a b a b a c a a b

a b a b a c a
Contd… n = 15
m=7

Step 12: i = 12, q = 5 P[q + 1] == T[i]

(if) P[6] == T[12]. Match. q++ = 6

b a c b a b a b a b a c a a b

a b a b a c a
Contd… n = 15
m=7

Step 13: i = 13, q = 6 P[q + 1] == T[i]

(if) P[7] == T[13]. Match. q++ = 7
b a c b a b a b a b a c a a b

a b a b a c a
• q == m. Yes.
– Pattern occurs with shift i – m =13 – 7 = 6.
– q = Π[q] = 1.
Contd… n = 15
m=7

Step 14: i = 14, q = 1 P[q + 1] == T[i]

(while) P[2] == T[14]. Mismatch. q = Π[q] = 0
b a c b a b a b a b a c a a b

Shifts skipped = 5 and first character is not a b a b a c a

compared. Comparison starts from P[2].
(if) P[1] == T[14]. Match. q++ = 1
b a c b a b a b a b a c a a b

a b a b a c a
Contd… n = 15
m=7

Step 15: i = 15, q = 1 P[q + 1] == T[i]

(if) P[2] == T[15]. Match. q++ = 2
b a c b a b a b a b a c a a b

a b a b a c a
Step 16: i = 16
Loop terminates.
Example
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

T: X Y X X Y X Y X Y Y X Y X Y X Y Y X Y X Y X X Y
P: X Y X Y Y X Y X Y X X

• Solve it using all the string matching algorithm

giving total
– Number of shifts and
– Number of character comparisons.

• For Rabin-Karp
– Σ = {0, 1}, q = 13, X = 0, Y=1
Naïve approach
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

T: X Y X X Y X Y X Y Y X Y X Y X Y Y X Y X Y X X Y
P: X Y X Y Y X Y X Y X X
P: X Y X Y Y X Y X Y X X
P: X Y X Y Y X Y X Y X X
P: X Y X Y Y X Y X Y X X
P: X Y X Y Y X Y X Y X X
P: X Y X Y Y X Y X Y X X
P: X Y X Y Y X Y X Y X X
P: X Y X Y Y X Y X Y X X
P: Total shifts X Y X Y Y X Y X Y X X
P: = 24 – 11 + 1 = 14 X Y X Y Y X Y X Y X X
P: Total character comparisons X Y X Y Y X. Y X Y X X
P: = 4 + 1 + 2 + 5 + 1 + 11 + 1 X Y X Y Y. X Y X Y X X
+ 3 + 1 + 1 + 5 + 1 + 11 + 1
P: X Y X Y Y X Y X Y X X
= 48
P: X Y X Y Y X Y X Y X X
 Σ = {0, 1}, q = 13, X = 0, Y=1
Rabin–Karp h = 211-1 mod 13 = 10

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

T: X Y X X Y X Y X Y Y X Y X Y X Y Y X Y X Y X X Y
0 1 0 0 1 0 1 0 1 1 0 1 0 1 0 1 1 0 1 0 1 0 0 1
P: X Y X Y Y X Y X Y X X • p = (29 + 27 + 26 + 24+ 22) mod 13 = 9
0 1 0 1 1 0 1 0 1 0 0 • T[1..11] = t0 = (29 + 26 + 24 + 22+ 21) mod 13 = 0
• T[2..12] = t1 = (2(0 – 10.0) + 1) mod 13 = 1
• T[3..13] = t2 = (2(1 – 10.1) + 0) mod 13 = 8
• p = 9.
• T[4..14] = t3 = (2(8 – 10.0) + 1) mod 13 = 4
• t7 = 9. Compare T[8..18] with P[1..11].
• T[5..15] = t4 = (2(4 – 10.0) + 0) mod 13 = 8
– T[8] = P[1] = X
– T[9] = P[2] = Y • T[6..16] = t5 = (2(8 – 10.1) + 1) mod 13 = 10
– T[10] = Y and P[3] = X. Mismatch • T[7..17] = t6 = (2(10 – 10.0) + 1) mod 13 = 8
• t12 = 9. Compare T[13..23] with P[1..11]. • T[8..18] = t7 = (2(8 – 10.1) + 0) mod 13 = 9
– Match. • T[9..19] = t8 = (2(9 – 10.0) + 1) mod 13 = 6
• T[10..20] = t9 = (2(6 – 10.1) + 0) mod 13 = 5
Total shifts = 24 – 11 + 1 = 14 • T[11..21] = t10 = (2(5 – 10.1) + 1) mod 13 = 4
• T[12..22] = t11 = (2(4 – 10.0) + 0) mod 13 = 8
Total character comparisons = 3 + 11 = 14 • T[13..23] = t12 = (2(8 – 10.1) + 0) mod 13 = 9
• T[14..24] = t13 = (2(9 – 10.0) + 1) mod 13 = 6
KMP
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

T: X Y X X Y X Y X Y Y X Y X Y X Y Y X Y X Y X X Y
P: X Y X Y Y X Y X Y X X
Π: 0 0 1 2 0 1 2 3 4 3 1
• i = 1, q = 0. T[1] = P[1] (Shift = 0). q = 1.
• i = 2, q = 1. T[2] = P[2] (Shift = 0). q = 2.
• i = 3, q = 2. T[3] = P[3] (Shift = 0). q = 3.
• i = 4, q = 3. T[4] ≠ P[4] (Shift = 0). q = Π[3] = 1.
T[4] ≠ P[2] (Shift = 2). q = Π[1] = 0.
T[4] = P[1] (Shift = 3). q = 1.
• i = 5, q = 1. T[5] = P[2] (Shift = 3). q = 2.
• i = 6, q = 2. T[6] = P[3] (Shift = 3). q = 3.
• i = 7, q = 3. T[7] = P[4] (Shift = 3). q = 4.
• i = 8, q = 4. T[8] ≠ P[5] (Shift = 3). q = Π[4] = 2.
T[8] = P[3] (Shift = 5). q = 3.
• i = 9, q = 3. T[9] = P[4] (Shift = 5). q = 4.
• i = 10, q = 4. T[10] = P[5] (Shift = 5). q = 5.
Contd…
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2

T: X Y X X Y X Y X Y Y X Y X Y X Y Y X Y X Y X X
P: X Y X Y Y X Y X Y X X
Π: 0 0 1 2 0 1 2 3 4 3 1 • i = 23 , q = 10 .
• i = 11, q = 5. T[11] = P[6] (Shift = 5). q = 6. T[23] = P[11] (Shift = 12). q = 11.
• i = 12, q = 6. T[12] = P[7] (Shift = 5). q = 7. Pattern found at shift 12. q = Π[11] = 1.
• i = 13, q = 7. T[13] = P[8] (Shift = 5). q = 8. • i = 24, q = 1.
• i = 14, q = 8. T[14] = P[9] (Shift = 5). q = 9. T[24] = P[2] (Shift = 22). q = 2.
• i = 15, q = 9. T[15] = P[10] (Shift = 5). q = 10.
• i = 16, q = 10. T[16] ≠ P[11] (Shift = 5). q = Π[10] = 3.
T[16] = P[4] (Shift = 12). q = 4.
• i = 17, q = 4. T[17] = P[5] (Shift = 12). q = 5.
• i = 18, q = 5. T[18] = P[6] (Shift = 12). q = 6. Total shifts = 6
• i = 19, q = 6. T[19] = P[7] (Shift = 12). q = 7.
• i = 20, q = 7. T[20] = P[8] (Shift = 12). q = 8. Total character comparisons = 28
• i = 21, q = 8. T[21] = P[9] (Shift = 12). q = 9.
• i = 22, q = 9. T[22] = P[10] (Shift = 12). q = 10.