KMP(克鲁特-莫里斯-普拉特算法)--子串的定位 效率O(n + m)
如主串S ababcabcacbab 子串P abcac
next[i]的值的确定 --- 通过求出p1...pk-1 = pj-k+1.....pj-1的最大k值
则上述abcac
1 0
2 1
3 3-1为ab 1
4 4-1为abc 1
5 5-1为abca 2 (首尾a)
试一试abcabc
1 0
2 1
3 3-1为ab 1
4 4-1为abc 1
5 5-1为abca 2 (首尾a)
6 6-1为abcab 3 (首尾ab)
再试试ababaaaba
1 0
2 1
3 3-1为ab 1
4 4-1为aba 2 (首尾a)
5 5-1为abab 3 (首尾ab)
6 6-1为ababa 4 (首尾aba)
7 7-1为ababaa 2 (首尾a)
8 8-1为ababaaa 2 (首尾a)
9 9-1为ababaaab 3 (首尾ab)
总结前2项为01是固定的,其他为(从左至右)首尾对应个数+1(个人解法)
-------------------------------------------------------------------------
#include <stdio.h> #include <string.h> int next[1000]; char S[] = "ooSusaketttt", P[] = "Susake"; void getnext() { int j = 1, k = 0, len = strlen(P); next[1] = 0; while (j < len) { if (k == 0 || P[k - 1] == P[j - 1]) { j++; k++; next[j] = k; } else k = next[k]; } } int KMP(int pos) { int i = pos, j = 1; getnext(); while (i <= strlen(S) && j <= strlen(P)) { if (j == 0 || S[i - 1] == P[j - 1]) { i++; j++; } else j = next[j]; } if (i > strlen(P)) return i - strlen(P); return -1; } int main(int argc, char *argv[]) { printf("%d\n", KMP(0)); return 0; }
原文：http://www.cnblogs.com/Cxx-Code/p/3630575.html