BCSE204L- Design and
Analysis of Algorithms
Dr. Iyappan Perumal
School of
Computer Science & Engineering
VIT,Vellore.
Module 3: String Matching Algorithms(5
Hours)
⚫ Naive String Matching
Algorithm
⚫ KMP–Knuth Morris Pratt Algorithm
⚫ Rabin- Karp Algorithm
⚫ Suffix Trees
String Matching
⚫ Text-editing programs frequently need to find
all occurrences of a pattern in the text.
⚫ Typically, the text is a document being edited,
and the pattern searched for is a particular
word supplied by the user.
⚫ Efficient algorithms for this problem called
“String Matching”
⚫ Example:
◦ Search for particular patterns in D N A sequences
◦ Internet search engines – find Web pages relevant to
queries.
Brute Force-Complexity
⚫ Given a pattern “M” characters in length, and a text “N”
characters in length...
⚫ Worst case: compares pattern to each substring of text of
length M. For example, M=5.
Total number of comparisons: M (N-M+1)
Worst case time complexity: O(MN)
Brute Force-Complexity(cont.)
⚫ Given a pattern M characters in length, and a text N
characters in length...
⚫ Best case if pattern found: Finds pattern in first M
positions of text. For example, M=5.
Total number of comparisons: M
Best case time complexity: O(M)
Alg PatternMatching Brute Force (S,P)
{
LS=[Link]
LP=[Link]
MAX=LS-LP+1
for(i=1 to max)
{
Flag= True; // boolean variable
for(j=1;j<=LP && Flag = =True; j++)
{
if P[j] = S[j+i-1]
Flag= False;
} // End of inner loop j
if (flag==True)
return i;
} // End of outer loop i
return 0;
}
Basic idea to K M P Algorithm
TEXT
A A A A A A A A A A A A A A A A A A A A A A B
PATTERN
A A A A A A B Iteration 1
Mismatch
A A A A A A B Iteration 2
In Naïve Based, We do right shift by one position to right
and start checking the PATTERN from the first
position…… Why to the Beginning????
Solution is : Just move 1 place before mismatch
Module 3: String Matching Algorithms(5
Hours)
⚫ Naive String Matching Algorithm
⚫ KMP–Knuth Morris Pratt
Algorithm
⚫ Rabin- Karp Algorithm
⚫ Suffix Trees
String Matching
⚫ Text-editing programs frequently need to find
all occurrences of a pattern in the text.
⚫ Typically, the text is a document being edited,
and the pattern searched for is a particular
word supplied by the user.
⚫ Efficient algorithms for this problem called
“String Matching”
⚫ Example:
◦ Search for particular patterns in D N A sequences
◦ Internet search engines – find Web pages relevant to
queries.
Problem in naive String Matching
Algorithm
TEXT
A A A A A A A D
i PATTERN
A A A D
j
• If characters are matched move both i and j.
• If character's are not matched, Move j to the starting
position and move i to the second position(where we
started)
• Note: In the above example A A A is repeating, Why we
should move j to the starting place?? Instead, is it possible to
move to previous place and check next alphabet is D or
not??
Knuth-Morris-Pratt Algorithm
⚫ One of the most popular string matching
algorithms used to find a Pattern in a Text
⚫ IDEA : Compares character by character from
left to right. But whenever a mismatch occurs,
it uses a pre-processed table called "Prefix
Table" to skip characters comparison while
matching.
⚫ Some times prefix table is also known as LPS
Table. Here LPS stands for "Longest proper
Prefix which is also sometimes called
Suffix".
Knuth-Morris-Pratt- Terminology to be
remembered
⚫ Pattern:-
abcdabc
⚫ proper prefixes:- a,ab,abc,abcd,abcda,abcdab
⚫ Proper suffixes:- c,bc,abc,dabc,cdabc,bcdabc
⚫ What we have to observe here??
⚫ If some beginning part of the pattern is
appearing anywhere else or not
Knuth-Morris-Pratt Algorithm
⚫ abcdabeabf
⚫ abcdeabfabc
⚫ aabcadaabe
⚫ aaaabaacd
⚫ abcdabca
⚫ aabaabaaa
⚫ Try out finding LPS table for the above
patterns
Knuth-Morris-Pratt Algorithm
TEXT
A B C E A B C D A B E A B C D A B C D A B D E
PATTERN
A B C D A B D
Steps for Creating LPS Table(Prefix Table)/π Table
⚫ Step 1 - Define a one dimensional array with the size equal
to the length of the Pattern. (LPS[size])
⚫ Step 2 - Define variables i & [Link] i = 0, j = 1 and LPS[0] = 0.
⚫ Step 3 - Compare characters at Pattern[i] and Pattern[j].
⚫ Step 4 - If both are matched then set LPS[j] = i+1 and
increment both i & j values by one. Goto to Step 3.
⚫ Step 5 - If both are not matched then check the value of
variable 'i'. If '0' then set LPS[j] = 0 and increment 'j' value
by one, if not '0' then set i = LPS[i-1]. Goto Step 3.
⚫ Step 6- Repeat above steps until all the values of LPS[] are
filled.
Creating LPS Table(Prefix Table) for Given Pattern
Character
PATTERN
A B C D A B D
0 1 2 3 4 5 6
index
Define LPS table of size 7 which is equal to length of the
pattern
LPS
0 1 2 3 4 5 6
Creating LPS Table(Prefix Table) for Given Pattern
STEP-1: Define Variables i and j,set i=0 & j=1 and LPS[0]=0
LPS
0 1 2 3 4 5 6 i=0
0 J=1
STEP-2: Compare pattern[i] with pattern [j]
pattern[0] with pattern [1] // i=0 & j=1
A with B
Both are not matching and also i=0, so set LPS[j]=0
and j=j+1
LPS
0 1 2 3 4 5 6 i=0
0 0 J=2
Creating LPS Table(Prefix Table) for Given Pattern
STEP-3: Compare pattern[i] with pattern [j]
pattern[0] with pattern [2] // i=0 & j=2
A with C
Both are not matching and also i=0, so set LPS[j]=0
and j=j+1
LPS
0 1 2 3 4 5 6
0 0 0
i=0
J=3
Creating LPS Table(Prefix Table) for Given Pattern
STEP-4: Compare pattern[i] with pattern [j]
pattern[0] with pattern [3] // i=0 & j=3
A with D
Both are not matching and also i=0, so set LPS[j]=0
and j=j+1
LPS
0 1 2 3 4 5 6
0 0 0 0
i=0
J=4
Creating LPS Table(Prefix Table) for Given Pattern
STEP-5: Compare pattern[i] with pattern [j]
pattern[0] with pattern [4] // i=0 & j=4
A with A
Both are matching, so set LPS[j]=i+1 and increment
i and j by one.
LPS
0 1 2 3 4 5 6
0 0 0 0 1
i=1
J=5
Creating LPS Table(Prefix Table) for Given Pattern
STEP-6: Compare pattern[i] with pattern [j]
pattern[1] with pattern [5] // i=1 & j=5
B with B
Both are matching, so set LPS[j]=i+1 and increment
i and j by one.
LPS
0 1 2 3 4 5 6
0 0 0 0 1 2
i=2
J=6
Creating LPS Table(Prefix Table) for Given Pattern
STEP-7: Compare pattern[i] with pattern [j]
pattern[2] with pattern [6] // i=2 & j=6
C with D
Both are N O T matching, and also i ! =0 , so set
i= LPS[i-1].// LPS[2-1]= LPS[1]= 0
LPS
0 1 2 3 4 5 6
0 0 0 0 1 2
i=0
J=6
Creating LPS Table(Prefix Table) for Given Pattern
STEP-8: Compare pattern[i] with pattern [j]
pattern[0] with pattern [6] // i=0 & j=6
A with D
Both are N O T matching, and also i =0 , so set
LPS[j]=0 and j=j+1
LPS
0 1 2 3 4 5 6
0 0 0 0 1 2 0
i=0
J=7
Once Table is filled, Stop the Process
Knuth-Morris-Pratt Algorithm
LPS Function or PREFIX Function(P)
LPS Function or PREFIX Function(P)
LPS Function or PREFIX Function(P)
LPS Function or PREFIX Function(P)
0
Knuth-Morris-Pratt Algorithm
TEXT
A B A B C A B C A B A B A B D
i
j Index, PATTERN & LPS TABLE VALUE
0 1 2 3 4 5
A B A B D
0 0 1 2 0
• If characters in ith and j+1th the position are
matched move both i and j.
• If character's in ith and j+1th are not matched, Move
j to the LPS value where j is pointing.
How to use LPS Table(Prefix Table)
⚫ LPS table is used to decide how many characters are to be
skipped for comparison when a mismatch has occurred.
⚫ When a mismatch occurs, check the LPS value of the previous
character of the mismatched character in the pattern.
⚫ If it is '0' then start comparing the first character of the
pattern with the next character to the mismatched
character in the text.
⚫ If it is not '0' then start comparing the character which is at
an index value equal to the LPS value of the previous
character to the mismatched character in pattern with
the mismatched character in the Text.
Knuth-Morris-Pratt Algorithm- Example
TEXT
A B C E A B C D A B E A B C D A B C D A B D E
PATTERN
A B C D A B D
LPS TABLE
0 1 2 3 4 5 6
0 0 0 0 1 2 0
Knuth-Morris-Pratt Algorithm- Step 1
Start Comparing first character of pattern with first
character of text from left to right
A B C E A B C D A B E A B C D A B C D A B D E
A B C D A B D
Mismatch occurred at pattern[3], so check LPS[2], it is 0
If it is 0, start comparing first character of pattern with
next character to the mismatched character in the text.
0 1 2 3 4 5 6
LPS TABLE
0 0 0 0 1 2 0
Knuth-Morris-Pratt Algorithm- Step 2
Start Comparing first character of pattern with next
character to the mismatched character in the text
A B C E A B C D A B E A B C D A B C D A B D E
A B C D A B D
Mismatch occurred at pattern[6], so check LPS[5], it is 2
If it is not 0, start comparing pattern[2] character with
mismatched character in the text.
0 1 2 3 4 5 6
LPS TABLE
0 0 0 0 1 2 0
Knuth-Morris-Pratt Algorithm- Step 3
LPS value is 2, no need to compare pattern[0] and
pattern[1]
A B C E A B C D A B E A B C D A B C D A B D E
A B C D A B D
Mismatch occurred at pattern[2], so check LPS[1], it is 0
If it is 0, start comparing first character of pattern with
next character to the mismatched character in the text.
0 1 2 3 4 5 6
LPS TABLE
0 0 0 0 1 2 0
Knuth-Morris-Pratt Algorithm- Step 4
Compare pattern[0] with next character in the text
A B C E A B C D A B E A B C D A B C D A B D E
A B C D A B D
Mismatch occurred at pattern[6], so check LPS[5], it is 2
If it is not 0, start comparing pattern[2] character with
mismatched character in the text.
0 1 2 3 4 5 6
LPS TABLE
0 0 0 0 1 2 0
Knuth-Morris-Pratt Algorithm- Step 5
Compare pattern[0] with next character in the text
A B C E A B C D A B E A B C D A B C D A B D E
A B C D A B D
Here all the characters of pattern matched with the
substring of the text which is starting from index 15
0 1 2 3 4 5 6
LPS TABLE
0 0 0 0 1 2 0
Knuth-Morris-Pratt Algorithm
KMP Matcher(T,P)
Knuth-Morris-Pratt Algorithm
Time Analysis
⚫ Preparing π table − O(m)
⚫ Parsing through the text (main string) − O(n)
⚫ Overall complexity − O(m + n)
Module 3: String Matching Algorithms(5
Hours)
⚫ Naive String Matching Algorithm
⚫ KMP–Knuth Morris Pratt Algorithm
⚫ Rabin- Karp Algorithm
⚫ Suffix Trees
String Matching
⚫ Text-editing programs frequently need to find
all occurrences of a pattern in the text.
⚫ Typically, the text is a document being edited,
and the pattern searched for is a particular
word supplied by the user.
⚫ Efficient algorithms for this problem called
“String Matching”
⚫ Example:
◦ Search for particular patterns in D N A sequences
◦ Internet search engines – find Web pages relevant to
queries.
Rabin Karp Algorithm
⚫ The Rabin-Karp string searching algorithm
calculates a hash value for the pattern, and for
each M-character subsequence of text to be
compared.
⚫ If the hash values are unequal, the algorithm
will calculate the hash value for next M-
character sequence.
⚫ If the hash values are equal, the algorithm
will do a Brute Force comparison between the
pattern and the M-character sequence.
⚫ In this way, there is only one comparison
per text subsequence, and Brute Force is
only needed when hash values match.
Rabin Karp Algorithm
⚫ Assign Numeric Codes to the characters in the
text and pattern
⚫ Ideally ASCII codes can be used.
⚫ Find a single value for the pattern (called hash
code) using a hash function
⚫ Find hash codes in the text for piece of pattern
length
◦ If hash codes match, check individual characters, else
take next piece of character.
Basic idea
TEXT
a a a a a b
Size=6
1 2 3 4 5 6
PATTERN
a a b 1+1+2 = 4
Size=3
1 2 3
Hash
Hash code
Finding Single Value of the Pattern ?? Function
a 1
Rolling Hash Function b 2
c 3
d 4
O(n-m+1) e 5
Drawback
TEXT
c c a c c a a e d b a
Size=11
1 2 3 4 5 6 7 8 9 10 11
PATTERN
d b a a 1
Size=3 b 2
1 2 3
c 3
d 4
Finding Single Value of the Pattern ??
e 5
Hash Code= 4+2+1= 7 f 6
g 7
h 8
????? Spurious Hits i 9
j 10
O(mn)
Rabin Karp Algorithm
TEXT
c c a c c a a e d b a
Size=11
1 2 3 4 5 6 7 8 9 10 11
PATTERN
d b a a 1
Size=3 b 2
1 2 3
c 3
Have to use Strong Hash function
d 4
to avoid spurious hits – Given by
Rabin Karp e 5
f 6
= 4*102 + 2*101 + 1*100
g 7
= P[1]*10m-1 + P[2]*10m-2 + P[3]* 10m-3 h 8
= 421 -> Hash code i 9
j 10
Average case: O(n-m+1) Base
Worst Case: O(mn) Value
Rabin Karp Algorithm
TEXT
c c a c c a a e d b a
Size=11
1 2 3 4 5 6 7 8 9 10 11
= 3*102 + 3*101 + 1*100
a 1
= 331 - Not match so move on
b 2
[[3*102 + 3*101 + 1*100]- 3*102]*10 + 3*100 c 3
d 4
Rolling Hash e 5
Function f 6
g 7
PATTERN h 8
Hash Code: 421
i 9
d b a
Size=3 j 10
1 2 3
Rabin Karp Matcher(T, P,d,q)
Rabin Karp Algorithm- Usage of Mod
Operation
⚫ Hash codes for very long pattern will be huge
numbers
⚫ Sometimes beyond system memory limits
⚫ Use a prime number (q) and make all
computations in modulo q arithmetic
⚫ So that the numbers will always be ≤ q
⚫ But the chances of spurious hits increase by this
modification
Rabin Karp Algorithm- Analysis
⚫ O(n + m − 1) in average case, if no spurious hits
⚫ In worst case, all can be spurious hits, defines
rolling hash function So the worst case
complexity is O(mn)
⚫ Generally the complexity of Rabin Karp would
be between O(n + m − 1) and O(mn)
Sufix trees
⚫ [Link]
ThTv0Y&t