Knuth–Morris–Pratt algorithm: Difference between revisions

Revision as of 09:34, 26 June 2003

Revision as of 07:46, 22 October 2003

Line 1:

ThisThe '''Knuth-Morris-Pratt [[string searching algorithm]]''' locates a pattern of characters within a string. It uses the fact that after finding the first mismatch, between pattern and string we already know the characters compared before to improve the efficiency of the search. We therefore will have to compare the pattern to itself to determine how many positions we have to move to the left.

'''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.

The following implementation is written in [[C programming language|C]]:

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;

Procedure InitNext(P)

for (q=2;q<=m;q++)

Input: Pattern P

{

while ((l>0) && (P[l+1] != P[q]))

next[1] = 0;

{

for (q=2;q<=m;q++)

l++ = next[l];

{

}

while ((l>0) && (P[l+1] != P[q]))

if (P[l+1] == P[q])

{

l = next[l]++;

} next[q] = l;

}

if (P[l+1] == P[q])

l++;

next[q] = l;

}