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
Sanskrit language

... The oldest surviving Sanskrit grammar is Paanini's c. 500 BC Astaadhyaayii[?] ("8 Chapter Grammar"). A form of Sanskrit called Epic Sanskrit is seen in the ...

 
 
 
This page was created in 22.2 ms