KMP完整代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int* build_prefix_table(const char* str_pat, int len_pat) {
int* prefix_table = (int*)calloc(1, sizeof(int) * len_pat);
int* tmp_table = (int*)calloc(1, sizeof(int) * len_pat);
if (NULL == prefix_table || NULL == tmp_table) {
perror("calloc()");
exit(1);
}
int i = 0, j = 1;
tmp_table[0] = 0;
while (j < len_pat) { // O(len_pat)
if (i == 0 && str_pat[i] != str_pat[j]) {
tmp_table[j] = 0;
j++;
}
else if (str_pat[i] == str_pat[j]) {
tmp_table[j] = i + 1;
i++;
j++;
}
else {
i = tmp_table[i - 1];
}
}
printf("prefix table: ");
for(int i = 0; i < len_pat; i++)
printf("%d ", tmp_table[i]);
// 把tmp_table抄录到prefix_table, 注意首项值为-1
prefix_table[0] = -1;
for (int i = 1; i < len_pat; i++) // O(len_pat)
prefix_table[i] = tmp_table[i - 1];
free(tmp_table);
return prefix_table;
}
int KMP(const char* str, const char* pat) {
int len_str = strlen(str); // O(len_str)
int len_pat = strlen(pat); // O(len_pat)
if (len_pat > len_str) {
fprintf(stderr, "len_pat > len_str\n");
return -1;
}
int i_str = 0, i_pat = 0;
int* prefix_table = build_prefix_table(pat, len_pat); // Tm = O(?)
while (i_str < len_str && i_pat < len_pat) { // O(len_pat)
if (str[i_str] == pat[i_pat]) {
i_str++;
i_pat++;
}
else if (str[i_str] != pat[i_pat] &&
prefix_table[i_pat] != -1) {
i_pat = prefix_table[i_pat];
}
else {
i_str++;
}
}
if (i_pat == len_pat)
return i_str - len_pat;
return -1;
}
int main() {
char string[] = { "abaacababcac" };
char pattern[] = { "abab" };
int pos = KMP(string, pattern);
if (-1 == pos)
printf("Not Found!\n");
else {
printf("\nposition in string: %d\n", pos);
printf("%s\n", string + pos);
}
return 0;
}
运行结果：