Knuth-Morris-Pratt algorithm
From Free media library
{{#switch: |Category = Pages in this category have | This page has }} been marked for eventual deletion.
{{#switch: |Category= They have
| It has}} been identified as reference material per the exclusion guidelines, which the community has decided to exclude from Wikisource (see "Inclusion of reference data on Wikisource"). These works will be phased out gradually; if you have found this page by following a link from another page, please go back and remove that link.{{#switch::Knuth-Morris-Pratt algorithm
|Category:Deletion requests/Reference data = |Wikisource:Scriptorium = |
}}
The Knuth-Morris-Pratt algorithm for string matching runs in O(m + n) time, where m is the length of the pattern and n is the length of the text to be searched. Compare this with the brute-force search time of O(mn) or the Boyer-Moore worst-case time of O(m + n).
External links:
[edit]
Ada (83 and 95)
pattern_match_knuth_morris_pratt_fixed_test.adb
[edit]
C
#include <stdio.h>
#include <stdlib.h>
const char *kmp_search(const char *text, const char *pattern)
{
int *T;
int i, j;
const char *result = NULL;
if (pattern[0] == '\0')
return text;
/* Construct the lookup table */
T = malloc((strlen(pattern)+1) * sizeof *T);
T[0] = -1;
for (i=0; pattern[i] != '\0'; i++) {
T[i+1] = T[i] + 1;
while (T[i+1] > 0 && pattern[i] != pattern[T[i+1]-1])
T[i+1] = T[T[i+1]-1] + 1;
}
/* Perform the search */
for (i=j=0; text[i] != '\0'; ) {
if (j < 0 || text[i] == pattern[j]) {
++i, ++j;
if (pattern[j] == '\0') {
result = text+i-j;
break;
}
}
else j = T[j];
}
free(T);
return result;
}