Agenda
• Introduction
• Functioning
• Example
• Exercise
Dr. Pavithra, Assistant Professor, SCOP 1
E, VIT
KMP Algorithm
• The idea behind the KMP algorithm is
that if there is any prefix same as suffix
and it will use the pattern to avoid the
unnecessary comparison.
• To complete the process ∏-table is used
which is also known longest prefix suffix.
Dr. Pavithra, Assistant Professor, SCOP 2
E, VIT
KMP Algorithm
• 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 suffix of Pq
That means ∏[q] is the length of the longest
prefix of P and is a proper suffix
Dr. Pavithra, Assistant Professor, SCOP 3
E, VIT
Practice on preparing the ∏ Table
• ababd
• aabaaab
• abcdabd
Dr. Pavithra, Assistant Professor, SCOP 4
E, VIT
Practice on KMP
• Given Text T:
abacbababababaacbacaababababaabababa
bababacac.
• Given Pattern P: abababa
Dr. Pavithra, Assistant Professor, SCOP 5
E, VIT
Practice on KMP
• Given Text T: ABC ABCDAB
ABCDABCDABDE
• Given Pattern P: ABCDABD
Dr. Pavithra, Assistant Professor, SCOP 6
E, VIT
Algorithm
Compute_Prefix(P)
1- m=P.length
2- Let ∏[1..m] be an array
3- ∏[1]=0
4- k=0
5- for q=2 to m
6- while k>0 and P[k+1]!=P[q]
7- k=∏[k]
8- if P[k+1]==P[q]
9- k=k+1
10- ∏[q]=k
11- return ∏
Dr. Pavithra, Assistant Professor, SCOP 7
E, VIT
Algorithm
KMP_Matcher(T,P)
1- m=P.length
2- n=T.length
3- ∏=compute_prefix(P)
4- q=0
2- for i=1 to n
6- while q>0 and P[q+1]!=T[i]
7- q=∏[q]
8- if P[q+1]==T[i]
9- q=q+1
10- if q==m
11- print “pattern occurs with shift” i-m
12- q=∏[q]
Dr. Pavithra, Assistant Professor, SCOP 8
E, VIT
Base for Robin Karp Algorithm
Text: aaaaab
Pattern: a a b
Dr. Pavithra, Assistant Professor, SCOP 9
E, VIT
Example problem of Robin Karp Algorithm
• Text T: c c a c c a d b a
• Pattern P: d b a
Dr. Pavithra, Assistant Professor, SCOP 10
E, VIT
Example problem of Robin Karp Algorithm
• Text T: a b c c d d a e f g
• Pattern P: c d d
Dr. Pavithra, Assistant Professor, SCOP 11
E, VIT
Robin Karp Algorithm
RABIN-KARP-MATCHER(T; P; d; q)
1- n = T.length
2- m = P.length
3- h = d^(m-1) %q
4- p = 0
5- t0 = 0
6- for i = 1 to m // preprocessing
7- p = (dp + P[i]) mod q
8- t0 = (dt0 + T[i]) mod q
9- for s = 0 to n-m // matching
10- if p == ts
11- if P [1..m] == T[s+1…s+m]
12- print “Pattern occurs with shift” s
13- if s<n-m
14- ts+1=(d(ts-T[s+1]h)+T[s+m+1]) mod q
15- if ts+1<0 then ts+1=ts+1 +q
Dr. Pavithra, Assistant Professor, SCOP 12
E, VIT
Example problem of Robin Karp Algorithm
• T: A B D C B
• P: D C
Dr. Pavithra, Assistant Professor, SCOP 13
E, VIT
Variation in Robin Karp Example
T = 31415926535
P = 26
Dr. Pavithra, Assistant Professor, SCOP 14
E, VIT
Variation in Robin Karp Example
T=2359023141526739921
P=31415
Dr. Pavithra, Assistant Professor, SCOP 15
E, VIT
Working of Robin Karp Algorithm
• Sequence of characters is taken and check
for the possibility of the presence of the
pattern P in text T.
• If there is possibility to find the string then
only character will be checked.
– Assign a numerical value to the characters in
the text and pattern.
– It calculate the hash value for the Pattern of
length m
Dr. Pavithra, Assistant Professor, SCOP 16
E, VIT
Working of Robin Karp Algorithm
– Calculate the hash value for the pattern p
– Calculate the hash value for the text T of
window size m.
– Compare the hash value of the pattern with
the hash value of the text. If the value matches
then character matching is performed.
– Calculate the hash value of the next window
by subtracting the first term and adding the
next term.
Dr. Pavithra, Assistant Professor, SCOP 17
E, VIT
Assumption of Robin Karp Algorithm
• It is making use of elementary number-
theoretic notions
• Assume that ∑ ={0,1,2,..,9}, so that each
character is a decimal digit.
• A pattern P[1..m], let p denote its
corresponding decimal value
Dr. Pavithra, Assistant Professor, SCOP 18
E, VIT
