2243 words - 9 pages

PKnuth-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

Deﬁnition History Components of KMP Algorithm Example Run-Time Analysis Advantages and Disadvantages References

Kranthi Kumar Mandumula

Knuth-Morris-Pratt Algorithm

Deﬁnition:

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 ...view middle of the document...

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 Preﬁx-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, preﬁx 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 preﬁx 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 Preﬁx function q←0 for i ←...

Find the perfect research document on any subject