Knuth-Morris-Pratt algorithm

Knuth-Morris-Pratt Algorithm This algorithm uses the fact that after finding the first mismatch, we already know the characters compared before. We therefore will have to compare the pattern to itself to determine how many positions we have to move to the left.

INPUT: Text T[0,n-1], Pattern P[0,m-1] Output alle matches of P in T

InitNext(P); j=0; for (i=1;i<=n;i++) {

   while ((j>0) && (P[j+1] != T[i]))
   {
      j=next[j];
   }
   if (P[j+1] == T[i])
      j++;
   if (j == m-1)
   {
      print "Found P";
      j = next[j];
   }

}

Procedure InitNext(P) Input: Pattern P

next[1] = 0; for (q=2;q<=m;q++) {

   while ((l>0) && (P[l+1] != P[q]))
   {
      l = next[l];
   } 
   if (P[l+1] == P[q])
      l++;
   next[q] = l;

}