我们假设要在主串中寻找子串出现的所有位置
我们记主串中的开始位置为匹配位置，如在 “abc” 中匹配 “bc” ，则匹配位置为 (2)
我们把匹配过程拆解为
以此，有显然的 O ( n m ) O(nm) O(nm) 算法
主串：ABCABCABD
子串：ABCABD
求 nxt 数组的过程可以先想象成对子串本身的一次 kmp
相同的思想，不同的实现之间有比较大的差别，以下给出最简练的代码和解释
示例代码的下标从0开始记
不难发现nxt天然即和下标有关，又和公共缀长度有关，是相等还是差1取决于下标起点
/*求nxt，s2是子串，m是子串长度*/
nxt[0]=nxt[1]=0;
for(int i=1;i<=m;i++){
int j=nxt[i];
while(j && s2[j]!=s2[i]) j=nxt[j];
//s2前后相同i+1就记j+1了，不同则j=nxt[j]，递归成子问题
nxt[i+1]=s2[j]==s2[i]?j+1:0;
//nxt=0表示不存在公共缀，从头开始
}
/*求匹配位置并输出*/
for(int i=0,j=0;i<n;i++){
while(j && s2[j]!=s1[i]) j=nxt[j];
if(s2[j]==s1[i]) j++;
if(j==m){
printf("匹配位置:%d\n",i-(m-1));
j=nxt[j];
}
}
图片来自"云端潜行" 遵循 CC 4.0 BY-SA 版权协议
这张图展示了KMP的匹配过程，从代码上看，最令人担心的就是每个 for 内部的 while，我们极端化，while 每次都 while 到头，情况如上图，那么我们发现每次 while 中
j
j
j 回退的次数最多是这个周期中
i
i
i 增加的个数，所以
j
j
j 改变量的和不超过
i
i
i 改变量的和，所以加起来是小于
2
N
2N
2N 的
nxt 数组和 KMP 匹配的过程类似
kmp 的后半部分就是在失配后，充分利用前面已经验证出来的匹配部分来减少试错
kmp 的前半部分求 nxt 也差不多
nxt 的设计上还有一种改进，假设子串 abaabaaba
nxt[6] 正常是 3，但是我们可以发现s[3]=s[6]，所以 6 失配，3 一定也会失配的，所以我们直接把nxt[6] 指到 nxt[3]
同理我们发现 s[9]=s[6] , 所以 nxt[9] 本来是指到 6 的，现在指到 nxt[6] ，因为 nxt[6] 又指到了 nxt[3]，所以结果是 nxt[9]=nxt[3]
这种改进是基于我们在观察失配时只考虑了失配前的已匹配串，但我们其实可以把失配的那个位置的字母也考虑进去。如果我们不处理这一优化，kmp 进行时会自己一路跳下去，如果这种情况出现多次，那么我们提前处理就会加速。
经测试，对于随机数据，可以加速 5-10%