Encyclopedia > Knuth-Morris-Pratt algorithm

  Article Content

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;
}



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
1904

... Dalí, artist May 17 - Jean Gabin[?], actor (+ 1976) May 21 - Fats Waller, pianist (+ 1943) May 21 - Robert Montgomery, actor (+ 1981) June 2 - Johnny ...

 
 
 
This page was created in 36.3 ms