KMP算法是用来解决字符串的匹配问题的，即在字符串S中寻找字符串P。形式定义：假设存在长度为n的字符数组S[0...n-1]，长度为m的字符数组P[0...m-1]，是否存在i，使得SiSi+1...Si+m-1等于P0P1...Pm-1，若存在，则匹配成功，若不存在则匹配失败。该问题经常出现在编辑器中，即常用的find或ctrl-F命令，所以字符串匹配算法的复杂度直接影响编辑器的效率。
首先考虑朴素字符串匹配的方法。其思想是：循环以字符数组S中的每一个字符作为起点，与字符数组P进行匹配。其代码如下所示：
int naiveStrMatch(char* s, char* p) {
int i, j;
int n = strlen(s), m = strlen(p);
for(i=; i<(n-m+); i++) {
for(j=; j<m&&s[i+j]==p[j]; j++);
if(j == m)
return i;
}
return -;
}
上面代码只返回首次匹配成功时，字符数组S的起点下标。在遍历数组S时，做了一步小的优化，即起点只能出现在[0...n-m]里。
假设进行下面的匹配：
| S0 | S1 | ... | Si-j | Si-j+1 | ... | Si-1 | Si | ... | Sn-1 |
| P0 | P1 | Pj-1 | Pj |
当Si与Pj不匹配，即Si≠Pj，此时根据上面的算法，S将把起点“回溯”至Si-j+1，P将向前“滑动”一位，即下次将是Si-j+1与P0进行比较。
可以看到上面算法的复杂度为O(n*m)，其在每次匹配失败时，都将S的起点进行回溯，从而重新匹配。而KMP算法的思想是：在匹配失败时，不回溯S而只滑动P，来降低算法复杂度。
再次考虑上面的情况，当Si与Pj不匹配，即Si≠Pj时：
若P0P1...Pj-2≠P1P2...Pj-1时，则朴素匹配的下一步，S将把起点“回溯”至Si-j+1，P将向前“滑动”一位，可直接跳过
若P0P1...Pj-3≠P2P3...Pj-1时，则朴素匹配的下下一步，S将把起点“回溯”至Si-j+2，P将向前“滑动”两位，也可直接跳过
直到P0P1...Pk-1=Pj-kPj-k+1...Pj-1时，S无需回溯，直接将P向前滑动j-k位，即Si与Pk进行比较，这便是KMP算法的核心思想。
为了算法方便，可引入next[]数组来记录满足P0P1...Pk-1=Pj-kPj-k+1...Pj-1的k值
k保证最大，可确保P滑动位数j-k最小，从而确保不会移动过多，错过匹配。
假设已知next[]数组，KMP算法如下代码所示：
int KMPStrMatch(char* s, char* p, int* next) {
int i, j;
int n = strlen(s), m = strlen(p);
/*for循环保证S不回溯*/
for(i=, j=; i<n; i++) {
/*当s[i]!=p[j]时，只滑动p至p[next[j]]*/
while(j>= && s[i]!=p[j])
j = next[j];
/*j++表示比较下一位*/
if(j==- || s[i]==p[j])
j++;
/*返回匹配成功的起点*/
if(j == m)
return i-m+;
}
return -;
}
接下来，问题将转换为如何求next[]数组。
方法一：直接根据上述定义来求，即对于每一个j，使K从j-1到1依次遍历，若满足P0P1...Pk-1=Pj-kPj-k+1...Pj-1，则break，并记录k值，具体代码如下：
void getNext1(char* p, int* next) {
int i, j, k;
int m = strlen(p);
next[] = -;
for(j=; j<m; j++) {
for(k=j-; k>; k--) {
for(i=; i<k&&p[i]==p[j-k+i]; i++);
if(i == k)
break;
}
next[j] = k;
}
}
方法二：将next[]数组的求解问题转换为KMP字符串匹配问题，然后使用递归的方式求解
假设已知next[j]=k，求next[k+1]，其计算过程如下图所示
| P0 | P1 | ... | Pj-k | Pj-k+1 | ... | Pj-1 | Pj | Pj+1 |
| P0 | P1 | ... | Pk-1 | Pk |
因为next[j]=k，所以P0P1...Pk-1=Pj-kPj-k+1...Pj-1
若Pk=Pj，则P0P1...Pk-1Pk=Pj-kPj-k+1...Pj-1Pj，所以next[j+1]=k+1
若Pk≠Pj，则该问题可类比于KMP字符串匹配问题，上图中第一行相当于字符串S，第二行相当于字符串P，此时S不回溯，只对P向前滑动，即滑动到Pnext[k]与Pj来进行比较，所以可递归的令k=next[k]，直到Pk=Pj时，next[j+1]=k+1
将上述思想转换为代码如下：
void getNext2(char* p, int* next) {
int j, k;
int m = strlen(p);
next[] = -; next[] = ;
k = ;
for(j=; j<m; j++) {
while(k>= && p[k]!=p[j])
k = next[k];
k++;
next[j+] = k;
}
}
至此，KMP算法的完整思想学习完毕。
KMP算法中next[]数组的其它应用：参考HDU 1358
题意：字符串S，若其某个前缀满足Ak，即前缀有k个字符串A连接而成，则输出前缀的长度和k。若某个前缀可有多个满足，则只输出最大的k
解决：假设A的长度为i，若长度为j的前缀满足Ak，即P0P1...Pi-1PiPi+1...P2i-1......P(k-1)iP(k-1)i+1...Pki-1Pj，此时j=k*i，根据上面的定义，可以知道next[j]=(k-1)*i，所以字符串A的长度i=j-next[j]，k=j/i，且j%i==0
如何证明此时的循环次数k为最大？使用反证法即可，若有更大的k，再推导出已知不成立
所以本题的代码如下：
#include<stdio.h> char s[];
int next[]; void get_next(int n){
int i, j, k;
next[] = -; next[] = ;
k = ;
for(j=; j<n; j++) {
while(k >= && s[j]!= s[k])
k = next[k];
k++;
next[j+] = k;
}
} int main() {
int case_num = , n;
int i, j, k;
scanf("%d", &n);
while(n) {
getchar();
case_num++;
scanf("%s", s);
printf("Test case #%d\n", case_num);
get_next(n);
for(i=; i<=n; i++) {
j = i - next[i];
k = i/j;
if(i%j == && k > ) {
printf("%d %d\n", i, k);
}
}
printf("\n");
scanf("%d", &n);
}
return ;
}