## KMP算法的基本原理

 B B C A B C D A B A B C D A B C D A B D E A

 B B C A B C D A B A B C D A B C D A B D E A B C D A B D

 字符 前缀 后缀 共有元素长度 A – – 0 AB A B 0 ABC A/AB BC/C 0 ABCD A/AB/ABC BCD/CD/D 0 ABCDA A/AB/ABC/ABCD BCDA/CDA/DA/A 1 ABCDAB A/AB/ABC/ABCD/ABCDA BCDAB/CDAB/DAB/AB/B 2 ABCDABD A/AB/ABC/ABCD/ABCDA/ABCDB BCDABD/CDABD/DABD/ABD/BD/D 0

 B B C A B C D A B A B C D A B C D A B D E A B C D A B D

 B B C A B C D A B A B C D A B C D A B D E A B C D A B D

 B B C A B C D A B A B C D A B C D A B D E A B C D A B D

 B B C A B C D A B A B C D A B C D A B D E A B C D A B D

P[0 ~ k-1] == P[j-k ~ j-1]

## nextval数组的求解思路

nextval[i]的求解需要比较s中next[i]所在位置的字符是否与s[i]的字符一致，如果一致则用s[next[i]]的nextval的值作为nextval[i]，如果不一致，则用next[i]做为nextval[i]。

nextval[i] = s[next[i]]==s[i]?nextval[s[next[i]]]:next[i]

## KMP算法的代码

KMP算法：可以实现复杂度为O(m+n)

#include<stdio.h>#include<string.h>void getNext(const char P[], int next[]){ int q, k; int m = strlen(P); next[0] = 0; for (q = 1, k = 0; q < m; ++q) { while (k > 0 && P[q] != P[k]) k = next[k - 1]; if (P[q] == P[k]) { k++; } next[q] = k; }}int kmp(const char T[], const char P[], int next[]){ int n, m; int i, q; n = strlen(T); m = strlen(P); getNext(P, next); for (i = 0, q = 0; i < n; ++i) { while (q > 0 && P[q] != T[i]) q = next[q - 1]; if (P[q] == T[i]) { q++; } if (q == m) // 输出找到的位置 还可以判断i == n - 1 未找到 { printf("Pattern occurs with shift:%d\n", (i - m + 1)); } }}int main(){ int i; int next[100] = { 0 }; char T[20], P[20]; scanf("%s%s", T, P); printf("%s\n", T); printf("%s\n", P); kmp(T, P, next); for (i = 0; i < strlen(P); ++i) { printf("%d ", next[i]); } printf("\n"); return 0;}