Knuth-Morris-Pratt Algorithm

Knuth, Morris and Pratt discovered first linear time string-matching algorithm by following a tight analysis of the na�ve algorithm. Knuth-Morris-Pratt algorithm keeps the information that na�ve approach wasted gathered during the scan of the text. By avoiding this waste of information, it achieves a running time of O(n + m), which is optimal in the worst case sense. That is, in the worst case Knuth-Morris-Pratt algorithm we have to examine all the characters in the text and pattern at least once.

 

The Failure Function

The KMP algorithm preprocess the pattern P by computing a failure function f that indicates the largest possible shift s using previously performed comparisons. Specifically, the failure function f(j) is defined as the length of the longest prefix of P that is a suffix of P[i . . j].

 

KNUTH-MORRIS-PRATT FAILURE (P)

Input:    Pattern with m characters
Output: Failure function f for P[i . . j]

i ← 1
j ← 0
f(0) ← 0
while i < m do
    if P[j] = P[i]
        f(i) ← j +1
         i ← i +1
          j← j + 1
else if
         j ← f(j - 1)
else
        f(i) ← 0
        i ← i +1

 

Read full article from Knuth-Morris-Pratt Algorithm