Knuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula
Knuth-Morris-Pratt Algorithm
Kranthi Kumar Mandumula
December 18, 2011
Kranthi Kumar Mandumula
Knuth-Morris-Pratt Algorithm
outline
Knuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula
Denition History Components of KMP Algorithm Example Run-Time Analysis Advantages and Disadvantages References
Kranthi Kumar Mandumula
Knuth-Morris-Pratt Algorithm
Denition:
Knuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula
Best known for linear time for exact matching. Compares from left to right. Shifts more than one position. Preprocessing approach of Pattern to avoid trivial comparisions. Avoids recomputing matches.
Kranthi Kumar Mandumula
Knuth-Morris-Pratt Algorithm
History:
Knuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula
This algorithm was conceived by Donald Knuth and Vaughan Pratt and independently by James H.Morris in 1977.
Kranthi Kumar Mandumula
Knuth-Morris-Pratt Algorithm
History:
Knuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula
Knuth, Morris and Pratt discovered rst linear time string-matching algorithm by analysis of the naive algorithm. It keeps the information that naive approach wasted gathered during the scan of the text. By avoiding this waste of information, it achieves a running time of O (m + n). The implementation of Knuth-Morris-Pratt algorithm is efcient because it minimizes the total number of comparisons of the pattern against the input string.
Kranthi Kumar Mandumula
Knuth-Morris-Pratt Algorithm
Components of KMP:
Knuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula
The prex-function : It preprocesses the pattern to nd matches of prexes of the pattern with the pattern itself. It is dened as the size of the largest prex of P [0..j 1] that is also a sufx of P [1..j ]. It also indicates how much of the last comparison can be reused if it fails. It enables avoiding backtracking on the string S .
Kranthi Kumar Mandumula
Knuth-Morris-Pratt Algorithm
m length [p ] a [1] 0 k 0 for q 2 to m do while k > 0 and p [k + 1] k a [k ] end while if p [k + 1] = p [q] then k k +1 end if a [q] k end for return Here a =
Knuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula
p [q] do
Kranthi Kumar Mandumula
Knuth-Morris-Pratt Algorithm
Computation of Prex-function with example: Knuth-Morris-Pratt
Algorithm Kranthi Kumar Mandumula
Let us consider an example of how to compute for the pattern p . Pattern a b a b a c a
I n i t i a l l y : m = length [ p]= 7 [1]= 0 k=0 where m, [1], and k are the length of the pattern, prex function and initial potential value respectively.
Kranthi Kumar Mandumula
Knuth-Morris-Pratt Algorithm
Knuth-Morris-Pratt Algorithm
Step 1 : q = 2 , k = 0 [2]= 0 q p 1 a 0 2 b 0 3 a 4 b 5 a 6 c 7 a
Kranthi Kumar Mandumula
Step 2 : q = 3 , k = 0 [3]= 1 q p 1 a 0 2 b 0 3 a 1 4 b 5 a 6 c 7 a
Kranthi Kumar Mandumula
Knuth-Morris-Pratt Algorithm
Knuth-Morris-Pratt Algorithm
Step 3 : q = 4 , k = 1 [4]= 2 q p 1 a 0 2 b 0 3 a 1 4 b 2 5 a 6 c 7 a
Kranthi Kumar Mandumula
Step 4 : q = 5 , k = 2 [5]= 3 q p 1 a 0 2 b 0 3 a 1 4 b 2 5 a 3 6 c 7 a
Kranthi Kumar Mandumula
Knuth-Morris-Pratt Algorithm
Knuth-Morris-Pratt Algorithm
Step 5 : q = 6 , k = 3 [6]= 1 q p 1 a 0 2 b 0 3 a 1 4 b 2 5 a 3 6 c 1 7 a
Kranthi Kumar Mandumula
Step 6 : q = 7 , k = 1 [7]= 1 q p 1 a 0 2 b 0 3 a 1 4 b 2 5 a 3 6 c 1 7 a 1
Kranthi Kumar Mandumula
Knuth-Morris-Pratt Algorithm
Knuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula
A f t e r i t e r a t i n g 6 times , t h e p r e f i x f u n c t i o n computations i s complete : q p 1 a 0 2 b 0 3 A 1 4 b 2 5 a 3 6 c 1 7 a 1
The running time of the prex function is O (m).
Kranthi Kumar Mandumula
Knuth-Morris-Pratt Algorithm
Algorithm
Knuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula
Step 1 : I n i t i a l i z e t h e i n p u t v a r i a b l e s : n = Length o f t h e Text . m = Length o f t h e P a t t e r n . = Prefix f u n c t i o n of pattern ( p ) . q = Number o f c h a r a c t e r s matched . Step 2 : D e f i n e t h e v a r i a b l e : q=0 , t h e b e g i n n i n g o f t h e match . Step 3 : Compare t h e f i r s t c h a r a c t e r o f t h e p a t t e r n w i t h f i r s t c h a r a c t e r o f text . I f match i s n o t found , s u b s t i t u t e t h e v a l u e o f [ q ] to q . I f match i s found , then i n c r e m e n t t h e v a l u e o f q by 1 . Step 4 : Check whether a l l t h e p a t t e r n elements are matched w i t h t h e t e x t elements . I f not , r e p e a t t h e search process . I f yes , p r i n t t h e number o f s h i f t s taken by t h e p a t t e r n . Step 5 : l o o k f o r t h e n e x t match .
Kranthi Kumar Mandumula
Knuth-Morris-Pratt Algorithm
n length [S ] m length [p ] a Compute Prex function q0 for i 1 to n do while q > 0 and p [q + 1] S [i ] do q a [q] if p [q + 1] = S [i ] then q q+1 end if if q == m then q a [q] end if end while end for Here a =
Kranthi Kumar Mandumula Knuth-Morris-Pratt Algorithm
Knuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula
Example of KMP algorithm:
Knuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula
Now let us consider an example so that the algorithm can be clearly understood. String b a c b a b a b a b a c a a b
Pattern a b a b a c a Let us execute the KMP algorithm to nd whether p occurs in S .
Kranthi Kumar Mandumula
Knuth-Morris-Pratt Algorithm
I n i t i a l l y : n = size of S = 15; m = s i z e o f p=7 Step 1 : i = 1 , q = 0 comparing p [ 1 ] w i t h S [ 1 ]
Knuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula
String b a c b a b a b a b a c a a b
Pattern a b a b a c a
P[1] does not match with S [1]. p will be shifted one position to the right. Step 2 : i = 2 , q = 0 comparing p [ 1 ] w i t h S [ 2 ]
String b a c b a b a b a b a c a a b
Pattern a b a b a c a
Kranthi Kumar Mandumula
Knuth-Morris-Pratt Algorithm
Knuth-Morris-Pratt Algorithm Step 3 : i = 3 , q = 1 comparing p [ 2 ] w i t h S [ 3 ] p [ 2 ] does n o t match w i t h S [ 3 ] Kranthi Kumar Mandumula
String b a c b a b a b a b a c a a b
Pattern a b a b a c a
B a c k t r a c k i n g on p , comparing p [ 1 ] and S [ 3 ] Step 4 : i = 4 , q = 0 comparing p [ 1 ] w i t h S [ 4 ] p [ 1 ] does n o t match w i t h S [ 4 ]
String b a c b a b a b a b a c a a b
Pattern a b a b a c a
Kranthi Kumar Mandumula
Knuth-Morris-Pratt Algorithm
Knuth-Morris-Pratt Algorithm Step 5 : i = 5 , q = 0 comparing p [ 1 ] w i t h S [ 5 ] Kranthi Kumar Mandumula
String b a c b a b a b a b a c a a b
Pattern a b a b a c a
Step 6 : i = 6 , q = 1 comparing p [ 2 ] w i t h S [ 6 ]
p [ 2 ] matches w i t h S [ 6 ]
String b a c b a b a b a b a c a a b
Pattern a b a b a c a
Kranthi Kumar Mandumula
Knuth-Morris-Pratt Algorithm
Knuth-Morris-Pratt Algorithm Step 7 : i = 7 , q = 2 comparing p [ 3 ] w i t h S [ 7 ] p [ 3 ] matches w i t h S [ 7 ] Kranthi Kumar Mandumula
String b a c b a b a b a b a c a a b
Pattern a b a b a c a
Step 8 : i = 8 , q = 3 comparing p [ 4 ] w i t h S [ 8 ]
p [ 4 ] matches w i t h S [ 8 ]
String b a c b a b a b a b a c a a b
Pattern a b a b a c a
Kranthi Kumar Mandumula
Knuth-Morris-Pratt Algorithm
Step 9 : i = 9 , q = 4 comparing p [ 5 ] w i t h S [ 9 ]
Knuth-Morris-Pratt Algorithm p [ 5 ] matches w i t h S [ 9 ] Kranthi Kumar Mandumula
String b a c b a b a b a b a c a a b
Pattern a b a b a c a
Step 1 0 : i = 10 , q = 5 comparing p [ 6 ] w i t h S [ 1 0 ]
p [ 6 ] doesn t matches w i t h S [ 1 0 ]
String b a c b a b a b a b a c a a b
Pattern a b a b a c a
B a c k t r a c k i n g on p , comparing p [ 4 ] w i t h S [ 1 0 ] because a f t e r mismatch q = [5] = 3
Kranthi Kumar Mandumula
Knuth-Morris-Pratt Algorithm
Knuth-Morris-Pratt Algorithm Step 1 1 : i = 11 , q = 4 comparing p [ 5 ] w i t h S [ 1 1 ] Kranthi Kumar Mandumula
String b a c b a b a b a b a c a a b
Pattern a b a b a c a
Step 1 2 : i = 12 , q = 5 comparing p [ 6 ] w i t h S [ 1 2 ]
p [ 6 ] matches w i t h S [ 1 2 ]
String b a c b a b a b a b a c a a b
Pattern a b a b a c a
Kranthi Kumar Mandumula
Knuth-Morris-Pratt Algorithm
Knuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula Step 1 3 : i = 13 , q = 6 comparing p [ 7 ] w i t h S [ 1 3 ]
p [ 7 ] matches w i t h S [ 1 3 ]
String b a c b a b a b a b a c a a b
Pattern a b a b a c a
pattern p has been found to completely occur in string S . The total number of shifts that took place for the match to be found are: i m = 13-7 = 6 shifts.
Kranthi Kumar Mandumula
Knuth-Morris-Pratt Algorithm
Run-Time analysis:
Knuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula
O (m) - It is to compute the prex function values. O (n) - It is to compare the pattern to the text. Total of O (n + m) run time.
Kranthi Kumar Mandumula
Knuth-Morris-Pratt Algorithm
Advantages and Disadvantages:
Knuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula
Advantages: The running time of the KMP algorithm is optimal (O (m + n)), which is very fast. The algorithm never needs to move backwards in the input text T. It makes the algorithm good for processing very large les.
Kranthi Kumar Mandumula
Knuth-Morris-Pratt Algorithm
Advantages and Disadvantages:
Knuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula
Disadvantages: Doesnt work so well as the size of the alphabets increases. By which more chances of mismatch occurs.
Kranthi Kumar Mandumula
Knuth-Morris-Pratt Algorithm
Knuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula
Graham A.Stephen, String Searching Algorithms, year = 1994. Donald Knuth, James H. Morris, Jr, Vaughan Pratt, Fast pattern matching in strings, year = 1977. Thomas H.Cormen; Charles E.Leiserson., Introduction to algorithms second edition , The Knuth-Morris-Pratt Algorithm, year = 2001.
Kranthi Kumar Mandumula
Knuth-Morris-Pratt Algorithm
