For The Best Thing In The World

Work Hard to Enjoy Them. bloom energy

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;

学习更多