To implement the knuth Morris Pratt, string matching algorithm.

51views

written 8.4 years ago by

teamques10 ★ 68k

• modified 8.4 years ago

i. This algorithm is named after scientist Knuth, Morris and Pratt.

ii. The basic idea behind this algorithm is to build a prefix array.

iii. This array is also called as Π array.

iv. Prefix array is build using the prefix and suffix information of pattern.

v. This algorithm achieves the efficiency of O (m +n) which is optimal in worst case.

Example:

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
Text	b	a	d	B	a	b	a	b	a	b	a	d	A	a	b
Pattern	a	b	a	B	a	d	a

Compute Prefix table:

0	1	2	3	4	5	6
A	b	a	b	a	D	A
0	0	1	2	3	0	0

Text [4] = Pattern [0] so increment.

Text [5] = Pattern [1] so increment.

Text [6] = Pattern [2] so increment.

Text [7] = Pattern [3] so increment.

Text [8] = Pattern [4] so increment.

Now Text [9] ≠ Pattern [5].

Now we backtrack, therefore we will be in position of Pattern [4]. Consult prefix table [4] = 3.

So we will compare Text [9] with Pattern [3].

Text [9] = Pattern [3] so increment.

Text [10] = Pattern [4] so increment.

Text [11] = Pattern [5] so increment.

Text [12] = Pattern [6] so increment.

Since entire pattern is matching with given text array at 6th position.

The pseudo code for KMP matcher algorithm:

ADD COMMENT EDIT