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
Urethra

... urethra develops between the penis and the scrotum. Infection of the urethra is urethritis, said to be more common in females than males. Urethritis is a common cause of ...

 
 
 
This page was created in 37.7 ms