首页 > 代码库 > KMP深入浅出
KMP深入浅出
这里看格式更佳：个人blog & 知乎上的提问
既然这样问，就默认你已经大致明白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]的作用。
下面有傻逼死：
"前缀"和"后缀"。
"前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。
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;
KMP深入浅出
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。