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
French resistance

... l'Armée[?] (ORA or Organization of Armed Resistance) - Giraudist ie. composed of supporters of French general Henri Giraud[?]. Francois Mitterrand joined it 1943. Ther ...

 
 
 
This page was created in 23 ms