知方号

知方号

KMP算法之Next数组详解

KMP算法之Next数组详解

最近刚好学到了kmp算法,对我来说还蛮难的,原理还好理解,就是next数组的求解让我很懵

旁听了一下隔壁班大佬的分享,觉得他们讲得特别好,就想来记录一下

最长公共前后缀

kmp算法首先要找“最长公共前后缀”,其定义为:A的“最长公共前后缀”是“A中以最后一个字符结尾的非前缀子串”与“A的前缀”能够匹配的最大长度。例:ababab我们从“最大长度”6开始向下枚举若答案是6。根据定义,“A中以最后一个字符结尾的非前缀子串”是ababab?我们注意到,ababab也算它自身的一个前缀因此,在枚举时,要从这个字符串的长度减一开始枚举!

若答案是5,则“非前缀子串”为babab。而“前缀”是ababa。两者不相等。

若答案是4,则“非前缀子串”为abab,而“前缀”是abab。两者相等。所以我们可以确定,字符串”ababab”的“最长公共前后缀”长度为4。

有什么用?

举例说明:有两个字符串

S: abaacababcacT: ababc首先,根据最长公共前后缀,我们写出T串的所有前缀的“最长公共前后缀”长度:T[0~0] = “a”,最长公共前后缀长度:0T[0~1] = “ab”,最长公共前后缀长度:0T[0~2] = “aba”,最长公共前后缀长度:1T[0~3] = “abab”,最长公共前后缀长度:2T[0~4] = “ababc”,最长公共前后缀长度:0我们把求得的这5个数记为X数组(因为它还不是next数组)

这个更改后的X数组就是next数组,下图是上面的执行

next数组的含义是:当S[i]和T[j]不相等,并且j不等于-1时,j指针该指向的位置,且i指针不动。

当然我们目前只是枚举,接下来如何用算法实现求next数组

求next数组

假设一个新的字符串R:       a b c a b d e a b c a b c fnext:  -1 0 0 0 1 ?我们要求next[5]

情况一 R[i-1] == R[next[i-1]]

比如R[5-1]=R[1],所以显然next[6]=next[5]+1=2

 

 

 情况二 若R[i-1]!=R[next[i-1]]

R:       a b c a b d e a b c a b c fnext: -1 0 0 0 1 2 ?我们发现R[i-1]和R[next[i-1]]并不相等。

用肉眼可以看出,我们在abcabd不管怎么取后缀,后缀的最后一个字符d,从来就没有在前面出现过。所以它不可能和任何一个前缀相等。所以next[6]才是0。

假设我们求到了这种程度R:       a b c a b d e a b c a b c fnext:  -1 0 0 0 1 2 0 0 1 2 3 4 5 ?发现R[2] == ‘c’。换言之,枚举next[13]时,我们发现6不行,5不行,4不行,其原因都在最后一个字符’c’不是前缀的最后一个字母。刚才我们发现R[next[12]],也就是R[5],和这个最后一个字符是不一样的但是,R[next[5]] = R[2] = ‘c’就和R[12]是一样的。也就是说,R[12] == R[next[next[12]]]。这不是巧合。可以证明,只要找到了这个’c’,且next[next[12]]=2,则R[13]就是2+1=3。并且可以证明,除了next[12]+1,next[next[12]]+1,next[next[next[12]]]+1…以外,next[13]不会有其他的答案了。只要多次迭代,就能求出next[13]。经过多次迭代,如果发现迭代到了-1这里还没有找到最后一个字符,那么我们直接让next[13]=-1+1=0就可以了。这也是我们让那个X[0]=-1的又一个原因。

总结

 

 

 这就是求整个next数组的详细过程了,匹配的过程大家应该都懂,就不说了。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至lizi9903@foxmail.com举报,一经查实,本站将立刻删除。