KMP深入浅出
这个是回答知乎上的提问 既然这样问，就默认你已经大致明白KMP的原理吧。 举个通俗的例子解释KMP算法中NEXT[J]：
字符串: abcx
子串: abcd
当比较到d与X的时候，最原始的算法是子串向后移动一位继续比较
字符串: abcx
子串: abcd
而KMP则利用已知信息abc前3个字符是相等的，j从0跳到3,向后移动3位，比较a与X
字符串: abcx
|
abcd
当例子变复杂一点的时候：
字符串: abcabx
子串: abcabz
根据kmp原理可知，子串应该向后移动到
字符串: abcabx
|
abcabz
这样的位置而不是
字符串: abcabx
|
abcabz
原因就是子串里面有重复的值(即”前缀”和”后缀”有相似)。
当子串是正常的时候，我们向后移动的位数应该就是子串比较了多少位直到不相等(就是j值)(懂kmp的你懂的。。)，如：
abcabd | abcabg | abcdefg |
abc | ab | de |
后移3位 | 后移两位 | 后移2位 |
但是，就是因为子串不是单纯的每个不相等(前后缀不相似)，所以就需要我们的next[j]了！！
比如: abcabgabcabx
abcabx
这里原本是可以直接向后移动j=5，5位的，
abcabgabcabx
|
abcabx
但是因为abcabx中有相似,所以只能向后移动5-2=3位了
abcabgabcabx
|
abcabx
而要减去的这个2,则是next[5]的所存储的东西！
所以next[j]的作用就是，保存当有相似子串时，要减去的数(相似度）
那么，对于不相似的情况，也可以范化为，相似度为0,next[j]=0, 所有子串比较到不相等的情况时，都后移j-next[j]位
这就是next[j]的作用。
下面有傻逼死：
1.”前缀”和”后缀”。
“前缀”指除了最后一个字符以外，一个字符串的全部头部组合；”后缀”指除了第一个字符以外，一个字符串的全部尾部组合。
2.”前缀”和”后缀”相似度，即next数组的值，即《部分匹配表》（Partial Match Table）是什么。
那么，如何来计算呢？
先明确"前缀"和"后缀"相似度是什么。
如在abcabx中，
当j=0时只有a，前缀和后缀都为空集，共有元素的长度为，next[j]=0;
当j=1时,ab的前缀是a,后缀是b，如上，next[j]=0;
当j=2时,abc的前缀是a,ab,后缀是bc,b,如上，next[j]=0;
当j=3时,abca的前缀是a,ab,abc,后缀是bca,ca,a, 前缀跟后缀有一个交集（相似）a，长度为1,所以next[j]=1;
当j=4时,abcab的前缀是a,ab,abc,abca,后缀是bcab,cab,ab,b, 前缀跟后缀有一个最大交集（相似）ab，长度为2,所以next[j]=2;
当j=6时,abcabx的前缀是a,ab,abc,abca,abcab,后缀是bcabx,cabx,abx,bx,共有元素的长度为，next[j]=0;