1.KMP算法的核心，是一个记录最大公共前缀值的next数组。我觉得理解KMP的最大障碍就是很多人在看了很多关于KMP的文章之后，仍然搞不懂next数组中的值代表了什么意思。这里我们抛开所有的枝枝蔓蔓，先来解释一下这个数据到底是什么。对于字符串“abababca”，我们考虑它的公共前缀，我先解释一下字符串的前缀和后缀。如果字符串A和B，存在A=BS，其中S是任意的非空字符串，那就称B为A的前缀。例如，”Harry”的前缀包括{”H”,”Ha”, ”Har”, ”Harr”}，我们把所有前缀组成的集合，称为字符串的前缀集合。同样可以定义后缀A=SB，其中S是任意的非空字符串，那就称B为A的后缀，例如，”Potter”的后缀包括{”otter”, ”tter”, ”ter”,”er”,”r”}，然后把所有后缀组成的集合，称为字符串的后缀集合。要注意的是，字符串本身并不是自己的后缀。有了这个定义，就可以说明PMT中的值的意义了。next数组中的值是字符串的前缀集合与后缀集合的交集中最长元素的长度。例如，对于”aba”，它的前缀集合为{”a”,”ab”}，后缀 集合为{”ba”, ”a”}。两个集合的交集为{”a”}，那么长度最长的元素就是字符串”a”了，长度为1，所以对于”aba”而言，它在next表中对应的值就是1。再比如，对于字符串”ababa”，它的前缀集合为{”a”, ”ab”,”aba”, ”abab”}，它的后缀集合为{”baba”, ”aba”, ”ba”, ”a”}， 两个集合的交集为{”a”,”aba”}，其中最长的元素为”aba”，长度为3。
2.我们再来看如何使用这个表来加速字符串的查找，以及这样用的道理是什么。如上图，要在主字符串"ababababca"中查找模式字符串"abababca"。如果在j处字符不匹配,主字符串中 i 指针之前的 S[j−1] 位就一定与模式字符串的第 T[1] 位至第 T[j−1]位是相同的(这里数组下标从1开始)。这是因为主字符串在 i 位失配，而此时在 next 数组中 next[j]记录的值正是j指向的子串的最长相等前后缀的长度值+1，也就意味着主字符串从 i−next[j] 到 i-1 这一段是与模式字符串的 1 到 next[j] 这一段是完全相同的。这样一来，我们就可以将中间的一些字符段的比较省略掉。具体的做法是，保持i指针不动，然后将j指针指向模式字符串的 next[j] 位即可。简言之，以图中的例子来说，在 i 处失配，那么主字符串和模式字符串的前边6位就是相同的。又因为模式字符串的前6位，它的前4位前缀和后4位后缀是相同的，所以我们推知主字符串i之前的4位和模式字符串开头的4位是相同的。就是图中的灰色部分。那这部分就不用再比较了。
3.有了上面的思路，我们就可以使用next数组加速字符串的查找了。我们看到如果是在j位失配，那么影响j指针回溯的位置的其实是第 j 位的 next[j] 值，因为 next[j] 储存的是最长相等前后缀的长度值，此时模式串 1 到 next[j] 必然和主串的 i−next[j] 到 i-1 这段相同，那么将 j 回溯到最长相等前后缀值的后一位就可以了，为了编程的方便，通常将数组下标设置从1开始。
具体的程序如下所示：
void get_next(char T[], int next[]) { //求next数组的过程完全可以看成字符串匹配的过程
int i = 1, j = 0; //即以模式字符串为主字符串，以模式字符串的前缀为目标字符串
next[1] = 0;
while (i < T.length) {
if (j == 0 || T[i] == T[j]) { //字符串匹配成功,那么当前的next值就是匹配成功的字符串的长度。
i++;
j++;
next[i] = j;
} else
j = next[j]; //匹配失败，回溯
}
}
int kmp(char S[], char T[], int next[]) {
int i = 1;
int j = 1;
while (i <= S.length && j <= T.length) {
if (j == 0 || S[i] == T[j]) { //当j回溯到0，说明没有公共前后缀，从头开始匹配
i++; //只要模式串和主串字符相等，依次往后比较
j++;
} else
j = next[j]; //当主串和模式串中失配时，将j回溯到最大公共前后缀的后一位
}
if (j > T.length)
return i - T.length;
else
return 0;
}
4.对于next数组，它还不是最完美的，还可以优化，因为在j根据next[j]的值回溯时，若回溯到的位置模式串的值仍然是同一个，而这个值已经是失配的了，那就没有必要再比较，可以直接把此时的next[j]的值改成前面回溯位置相同的值，放到一个新数组nextval[]中。
void get_nextval(char T[],int next[]){
nextval[1] = 0;
for(int j = 2;j < T.length;j++){
if(T.ch[next[j]] == T.ch[j]) //回溯到具有相同字符时
nextval[j] = nextval[next[j]]; //因为在这个字符已经比较失败，避免多余比较
else
nextval[j] = next[j];
}
}