Content deleted Content added
Ryan Reich (talk | contribs) Add C code example to the search algorithm. |
|||
Line 59:
The second branch of step 2 executes once each time a comparison is not a match; the first branch, likewise, executes once for each match. It is clear from the operations performed in the second branch that <math>m + i</math> is nondecreasing with successive iterations of step 2; therefore, since <math>i</math> actually increases each time the first branch executes, the index <math>m + i</math> of the character currently under scrutiny increases between successive iterations of the first branch. Hence a character which has once been matched is never subjected to comparison again. It follows that the first branch also executes at most once for each character of <math>S</math>, hence no more than <math>l</math> times. So step 2 executes at most <math>2l</math> times. As step 1 executes merely once, and step 3 executes each time step 2 does except when the algorithm exits, the number of steps performed by the algorithm in searching <math>S</math> is at most <math>4l</math>; hence the search algorithm exits in <math>O(l)</math> time.
===A code example of the search algorithm===
Sample [[C programming language|C]] code for an implementation of this algorithm is given below. In order to satisfy the natural limitations on the bounds of C arrays, <math>T[i]</math> in the code is equivalent to <math>T[i + 1]</math> above.
int kmp_search(char *P, char *S)
{
extern int T[];
int m = 0;
int i = 0;
while (S[m + i] != '\0' && P[i] != '\0') {
if (S[m + i] == P[i]) {
++i;
} else {
m += i - T[i];
i = T[i];
}
}
return m;
}
==The "partial match" table==
| |||