那么通过观察来思考：每当临时匹配串（已知的）前后有重复的时候，那么只需 把模式串 T 直接移动到后缀刚刚开始有重复的位置（设移动距离为 d），i 不回溯。也就是j 直接反向的回溯距离 d，亮着等价的。为什么这样？
因为，在字符串搜索和匹配的时候，经常有前后重复的时候，前缀和后缀重复！如倒数第3图的已知的临时匹配串abca，前后缀 a 重复！此时没必要再用模式串的首位a去和S 的 b 比较了，直接和前后缀子串第一次有重复的位置比较（设子串右移距离 d），也就是 a 处。如果还那么顺次比较，是做无用功！此时思考如何实现这个逻辑，找到对应的j 回溯的距离 d。这个距离 d 就是前后重复的字符串的距离。
设置一个数组next来返回模式串的 j 应该回溯的位置
若令数组next[j]=k，则next[j]表明当模式中第j个字符与主串中相应字符失配时，在模式中需要重新和主串中该字符进行比较的字符的位置。
得到 KMP 模式匹配算法的实现思路(区别就是 next 函数）
那么问题来了，如何实现 next数组 ，生成对于的 j回溯的位置，从前面的讨论可知，next数组值仅取决于模式串本身，而与主串无关。
j 的回溯距离d 等于模式串中临时匹配串长(也就是j） 减去 相同的前后缀子串中的最大子串长度S（两个最大子串的距离），next 的值就是 j - j + S =S因此要计算next函数的返回值，就要找出前缀和后缀相同的最大子串的长度。
这个查找过程实际上仍然是模式匹配，只是匹配的模式与目标在这里是同一个串S。（这里遵守 c 的规定，数组都是默认下标0开始存储）
//计算 next 数组：根据待匹配的字符串，求出对应每一位的最大相同前后缀的长度
void computeNext(char *str, int next[])
{
}
int strKMPCompare(char *strMain, char *strSub, int index, int next[])
{
int iMain = index;
int jSub = 0;
int lenMain = getLength(strMain);
int lenSub = getLength(strSub);
while ((iMain >= 0 && iMain <= lenMain - 1) && ((jSub >= 0 && jSub <= lenSub - 1))){
if (strMain[iMain] == strSub[jSub]) {
iMain++;
jSub++;
}else{
//主串的 i 不回溯！
//计算 next 数组
computeNext(strSub, &next[0]);
jSub = next[jSub];
}
}
//如果匹配 ok，肯定子串先比完。
if (jSub > lenSub - 1) {
return iMain - lenSub;//得到的就是匹配 ok 后，主串里第一个和模式串第一个字符匹配的字符的位置
}else{
return 0;//匹配失败
}
}