**Knuth Morris Pratt Algorithm**

Knuth Morris Pratt Algorithm is the important topic of the Analysis & Design of Algorithm. Moreover, freestudy9 has all kind of important information and topic related to it.

- Knuth, Morris, and Pratt proposed a linear time algorithm for the string matching problem.
- A matching time of O(n) is achieved by avoiding comparisons with elements of ‘T’ that have previously been involved in comparison with some element of the pattern ‘P’ to be matched. i.e., backtracking on the text ‘S’ never occurs.

**The prefix function, π**

The prefix function, π for a pattern encapsulates knowledge about how the pattern matches against shifts of itself. This information can use to avoid useless shifts of the pattern ‘P’. In other words, this enables avoiding backtracking on the text ‘T’.

**The KMP Matcher**

With text ‘T’, pattern ‘P’ and prefix function ‘π’ as inputs, finds the occurrence of ‘P’ in ‘T’ and returns the number of shifts of ‘P’ after which occurrence found.

**KMP-MATCHER(T, P) **

- n ← length[T]
- m ← length[P]
- π ← COMPUTE-PREFIX-FUNCTION(P)
- q ← 0 //Number of characters matched.
- for i ← 1 to n //Scan the text from left to right.
- do while q > 0 and P[q + 1] ≠ T[i]
- do q ← π[q] //Next character does not match.
- if P[q + 1] = T[i]
- then q ← q + 1 //Next character matches.
- if q = m //Is all of P matched?
- then print “Pattern occurs with shift” i – m
- q ← π[q] //Look for the next match.

**COMPUTE-PREFIX-FUNCTION(P) **

- m ← length[P]
- π[1] ← 0
- k ← 0
- for q ← 2 to m
- do while k > 0 and P[k + 1] ≠ P[q]
- do k ← π[k]
- if P[k + 1] = P[q]
- then k ← k + 1
- π[q] ← k
- return π

**Example** **for Knuth Morris Pratt Algorithm**

- For the pattern P = ababababca and q = 8. Figure (a) the π function for the given pattern.
- Since π [8] = 6, π [6] = 4, π [4] = 2, and π [2] = 0, by iterating π we obtain π*[8] = {6, 4, 2, 0}. Figure (b)
- So, We slide the template containing the pattern P to the right and note when some prefix P
_{k}of P matches up with some proper suffix of P_{8}; this happens for k = 6, 4, 2, and 0. - In the figure, the first row gives P and the dotted vertical line drawn just after P
_{8}. - Also, Successive rows show all the shifts of P that cause some prefix P
_{k}of P to match some suffix of P_{8}. - Moreover, Successfully matched characters are shown shaded Vertical lines connect aligned matching characters.
- Thus, {k: k<q and P
_{k}⊃ P_{q}} = {6, 4, 2, 0}. π*[q] = {k : k<q and P_{k}⊃ P_{q}} for all q.

**Related Terms**

ADA Algorithms, String Matching with Finite Automata, Naive String Matching Algorithm, Rabin-Karp Algorithm

## Leave a Reply