String Matching Algorithms

• The Naïve string-matching algorithm

• The Rabin Karp algorithm
• The Knuth-Morris-Pratt algorithm
 String and pattern matching Algorithm

• String matching algo --- Text Processing

• Text processing is done in compilation of program
• Text processing is an important activity is software design and in
system design also.
• String matching means finding one or more occurrence of a string in
the text.
• These occurrences are called as pattern.
String matching Algorithm
• The naive method
• Rabin-Karp method
• The Boyer-Moore-Algorithm
• Finite automation for string matching
• Knuth – Morris – Pratt method
The naive method
• Simplest method works using Brute force approach
• This algo performs a checking at all positions in the text between 0 to
n-m
• After each attempt , it shifts the pattern by exactly one position to the
right.
• Example
The naive method
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
R A M A M L I K E s M A N G O

M A N G 0

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
R A M A M L I K E s M A N G O

M A N G 0
The naive method
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
R A M A M L I K E s M A N G O

M A N G 0

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
R A M A M L I K E s M A N G O

M A N G 0
The naive method
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
R A M A M L I K E s M A N G O

M A N G 0

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
R A M A M L I K E s M A N G O

M A N G 0
• Best case
• Text = dddddddddddd
aaa
• Pattern= aaa
The naive method
• Algorithm Naïve ( T[1..n],P[1..m])
{
// problem description: This algo finds the string
matching using Naïve method
// Input: The array text T and pattern P
for(s:= 0 to n-m) do
{
if(P[1..m] = T[s+1 …s+m] then
print(“Pattern finding with shift “ ,s)
}
} // end of algorithm
The naive method
• Analysis
worst case : m comparisons
O((n-m+1)*n)) = O(mn)

• Analysis
Average case : O(n)
Basic Notations & Terminologies
• Sigma star : set of all finite length strings formed using
input set sigma
• Zero length string : empty or null string , it is
denoted by epsilon
• | a| : length of string a
• Concatenation: con. Of string x and y
denoted by xy with length |x| +|y|
Basic Notations & Terminologies
• Prefix of string : Previously occurring string
eg. w[a.

• Suffix of string : String occurring after

particular string
eg. w]a.
Knuth-Morris-Pratt Algorithm
• In pattern matching algo like Naïve / Boyer Moore , we compare the
pattern characters that do not match in the text and on occurrence of
mismatch we simply throw a way the info. And restart the
comparision , for another set of chars from the text.
• Reduces the efficiency of pattern matching algo.
• KMP algo came up which avoids the repeated comparison of chars
Knuth-Morris-Pratt Algorithm
Basic idea
• To build prefix array(pi array), using prefix and suffix info. Of pattern
• Efficiency : O(m+n)
Optimal in worst case

• How to compute the prefix array for given pattern

• Consider the pattern “abadab”

0 1 2 3 4 5

a b a d a b

Initially we will put 0 in oth location of prefix array

Consider the string ab

Prefix : - a
Suffix : - b

No match of prefix and suffix

Hence we will put 0 in the in the prefix array at
1st location

0 1 2 3 4 5

a b a d a b

0 0
Consider the string aba

Prefix : - a ab
Suffix : - a ba

The length of matching prefix suffix is 1

Hence make entry 1 in prefix table

0 1 2 3 4 5

a b a d a b

0 0 1
Consider the string abad

Prefix : - a ab aba
Suffix : - d ad bad

The length of matching prefix suffix is 0

Hence make entry 0 in prefix table

0 1 2 3 4 5

a b a d a b

0 0 1 0
Consider the string abada

Prefix : - a ab aba abad

Suffix : - a da ada bada

The length of matching prefix suffix is 1

Hence make entry 1 in prefix table

0 1 2 3 4 5

a b a d a b

0 0 1 0 1
Consider the string abadab

Prefix : - a ab aba abad abada

Suffix : - b ab dab adab badab

The length of matching prefix suffix is 2

Hence make entry 2 in prefix table

0aba 1 2 3 4 5

a b a d a b

0 0 1 0 1 2
 Algorith for Prefix array
Algorithm Compute_prefix(char p[size])
Problem description : This algorithm computes prefix table for given pattern
// Input:pattern p
//output:prefix table for given pattern
prefix_table[0] 0
For(q 1 to m) do // m is the length of pattern
{
while(k>0 AND p[k] !=p[q]
k prefix_table[k-1]
if(p[k]=p[q]) then
k k+1
prefix_table[q]=k
}return prefix_table
• Comparing chars of pattern against Text
• Eg.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
b a d b a b a b a b a d a a b
a b a b a d a
• Compute the prefix table

0 1 2 3 4 5 6

a b a b a d a

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

b a d b a b a b a b a d a a b

a b a b a d a
• Compute the prefix table

0 1 2 3 4 5 6

a b a b a d a

0 0 1 2 3 0 1

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

b a d b a b a b a b a d a a b

a b a b a d a
Comparing a and b , as it is not matching , we wil
compare Text[1] with pattern[0]

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

b a d b a b a b a b a d a a b

a b a b a d a

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

b a d b a b a b a b a d a a b

a b a b a d a

Matching , so we will compare Text[2] with pattern[1]

As Text[2] is not matching with pattern[1] , we will
backtrack on pattern and compare pattern[0] with
Text[3]

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

b a d b a b a b a b a d a a b

a b a b a d a

0 1 2 3 4 5 6

a b a b a d a

0 0 1 2 3 0 1
Again Text[3] is not matching with pattern[0] , will then
ask prefix_table[0] for the location of pattern. As
prefix_table[0] is 0 , so we compare pattern[0] with
Text[4]

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

b a d b a b a b a b a d a a b

a b a b a d a
Text[4] matches with pattern[0] . Increment i and j
Text[9] is not matches with pattern[5]

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

b a d b a b a b a b a d a a b

a b a b a d a

j 0 1 2 3 4 5 6

Hence we backtrack on pattern array , that means j will be positioning on

location 4 .
Consult prefix _table[4] which denotes the value 3 . That indicates , compare
pattern[3] with current i position text array char . Hence we will compare
Text[9] with pattern[3], which is matching
Text[10] matches with pattern[4] . Increment i and j
Text[11] matches with pattern[5] . Increment i and j
Text[12] matches with pattern[6] . Increment i and j
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

b a d b a b a b a b a d a a b

a b a b a d a

j 0 1 2 3 4 5 6

Thus we have reached on the last char of pattern , at the same time i is
positioned at loc 12 in the text array
Hence we can declare that a match of pattern is found in the text at
i – length of pattern + 1
i.e. 12 – 7 + 1 = 6
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

b a d b a b a b a b a d a a b

a b a b a d a

0 1 2 3 4 5 6

Thus required pattern matches at location 6 in text

array using KMP algo.
Algorithm kmp_match(char t[50],char p[10])
//Problem description: This is a KMP pattern matching algorithm
// The Array of Text and pattern denoted by t and p variables
//Output: The starting location at which the matched pattern is found
J:=0
n=strlen(t)
m=strlen(p)
Prefix_table = Create prefix_table(p)
for( i=0 to i<n) do
{
while(j>0 AND p[j]!=t[i])do
j:=prefix_table[j-1]
if(p[j]==t[i])then
j++
if(j==m) then
{
write (“Pattern is present in the text at:”)
write(i=m+1)
j:=prefix_table[j-1] // consult prefix_table for positioning the pointer in the pattern array
}
}
Rabin Karp Algorithm
• Rabin Karp is a pattern matching algorithm
• The problem is if a text is given and pattern is given then we have to
find whether the pattern is present in the given string or not.
• Basic idea
• Example:
Text = a a a a a b //length of text=6
pattern = a a b // length of pattern=3
Rabin Karp Algorithm
Text = a a a a a b

pattern = a a b
a=1
a a b b=2
1+1+2=4 c=3
This value 4 is called as Hash code d=4
And the procedure to get this value 4 is called as function h(p) e=5
f=6
This hash function we use to find the pattern inside the text g=7
h=8
Now consider the text i=9
Text = a a a a a b J=10
1+ 1+1=3
So 3 is not equal to 4 , does not match , slide the pattern towards
right
Text = a a a a a b
Again value = 3 , does not match
Rabin Karp Algorithm
• Text = a a a a a b
• Again value = 3 , does not match , slide towards right
• Text = a a a a a b again not matches , so slide
• Text = a a a a a b
1 + 1 + 2 =4 // here 4=4 matches
Now compare the alphabet of pattern with text , it matches
So pattern found
Sliding is called as rolling hash function
O(n-m+1)
Rabin Karp Algorithm
• Drawback of Rabin Karp algorithm a=1
e.g. b=2
c=3
Text = C C A C C A A E D B A and Pattern= DBA d=4
e=5
Pattern = D B A f=6
g=7
4+2+1 =7 h=8
i=9
J=10
Rabin Karp
Text = C C A C C A A E D B A
3+3+1=7 here 7=7 but alphabets are not matching
Rabin Karp Algorithm
Text = C C A C C A A E D B A
3+1+3= 7 here 7=7 but alphabets are not matching
Text = C C A C C A A E D B A
1+3+3= 7 here 7=7 but alphabets are not matching
This is called as spurious hits
O(m*n)
How to avoid spurious hits?
Rabin Karp Algorithm
Pattern = D B A
4*102 + 2*101 + 1*100
400 +20+1 =421
That is p[1]X10m-1 + p[2]X 10 m-2 + p[3]X10m-0

where m=length of pattern