数据结构中严蔚敏第三版中 主串和模式串的匹配KMP算法

Question

主串是acabaabcaabaabcac 用i标记
模式串abaabcac 用j标记
next[j]具体是怎么求得的呢？ 为什么next[6]=3; next[7]=1？
请详细解答 通俗易懂的好
书上说的太迷茫

Answer 1

我当初学KMP的时候，有一个比较通俗的理解。
首先，可以肯定的是，next是模式串的事，跟主串无关。。。
模式串（对齐）abaabcac
下标序号分别为01234567
next[i]的值，为模式串0~i-1的前缀串中，前next[i]个字符，与后next[i]个字符，组成的串完全相等的，最大的值。当然，next[i]是小于整个前缀串长度的。。。
我用程序跑出来，这个模式串的next如下：
下标 字符 next[i]
0 a -1
1 b 0
2 a 0
3 a 1
4 b 1
5 c 2
6 a 0
7 c 1
对于next[0]与next[1]，无意义
next[2]，看前两个字符ab，前1与后1不同，故取0。
next[3]，对于aba，前1与后1相同，但取长度2就不同了，故next[3]=1。
以此类推，手算的话，就是枚举i-2~0的长度值，截取前缀串进行比较。
楼主所说的next[6]=3是不是算错了。。。- -追问

还是不懂啊
next的值到底是怎么计算的啊
next[4]怎么会是1呢
还有next[6]=0？

追答

next[i]的值，为模式串0~i-1的前缀串中，前next[i]个字符，与后next[i]个字符，组成的串完全相等的，最大的值。当然，next[i]是小于整个前缀串长度的。。。
这是个通俗理解。。。

追问

能不能把next[0]~next[8]的值都讲一遍
谢谢了

Answer 2

首先，可以肯定的是，next是模式串的事，跟主串无关。。。
模式串（对齐）abaabcac
下标序号分别为01234567
next[i]的值，为模式串0~i-1的前缀串中，前next[i]个字符，与后next[i]个字符，组成的串完全相等的，最大的值。当然，next[i]是小于整个前缀串长度的。。。
我用程序跑出来，这个模式串的next如下：
下标 字符 next[i]
0 a -1
1 b 0
2 a 0
3 a 1
4 b 1
5 c 2
6 a 0
7 c 1
对于next[0]与next[1]，无意义
next[2]，看前两个字符ab，前1与后1不同，故取0。
next[3]，对于aba，前1与后1相同，但取长度2就不同了，故next[3]=1。
以此类推，手算的话，就是枚举i-2~0的长度值，截取前缀串进行比较。
楼主所说的next[6]=3是不是算错了。。。- -

Answer 3

我当初学KMP的时候，有一个比较通俗的理解。
首先，可以肯定的是，next是模式串的事，跟主串无关。。。
模式串（对齐）abaabcac
下标序号分别为01234567
next[i]的值，为模式串0~i-1的前缀串中，前next[i]个字符，与后next[i]个字符，组成的串完全相等的，最大的值。当然，next[i]是小于整个前缀串长度的。。。
我用程序跑出来，这个模式串的next如下：
下标 字符 next[i]
0 a -1
1 b 0
2 a 0
3 a 1
4 b 1
5 c 2
6 a 0
7 c 1
对于next[0]与next[1]，无意义
next[2]，看前两个字符ab，前1与后1不同，故取0。
next[3]，对于aba，前1与后1相同，但取长度2就不同了，故next[3]=1。
以此类推，手算的话，就是枚举i-2~0的长度值，截取前缀串进行比较。
楼主所说的next[6]=3是不是算错了。。。- -

Answer 4

首先，可以肯定的是，next是模式串的事，跟主串无关。。。
模式串（对齐）abaabcac
下标序号分别为01234567
next[i]的值，为模式串0~i-1的前缀串中，前next[i]个字符，与后next[i]个字符，组成的串完全相等的，最大的值。当然，next[i]是小于整个前缀串长度的。。。
我用程序跑出来，这个模式串的next如下：
下标 字符 next[i]
0 a -1
1 b 0
2 a 0
3 a 1
4 b 1
5 c 2
6 a 0
7 c 1
对于next[0]与next[1]，无意义
next[2]，看前两个字符ab，前1与后1不同，故取0。
next[3]，对于aba，前1与后1相同，但取长度2就不同了，故next[3]=1。
以此类推，手算的话，就是枚举i-2~0的长度值，截取前缀串进行比较。

Answer 5

我当初学KMP的时候，有一个比较通俗的理解。
首先，可以肯定的是，next是模式串的事，跟主串无关。。。
模式串（对齐）abaabcac
下标序号分别为01234567
next[i]的值，为模式串0~i-1的前缀串中，前next[i]个字符，与后next[i]个字符，组成的串完全相等的，最大的值。当然，next[i]是小于整个前缀串长度的。。。
我用程序跑出来，这个模式串的next如下：
下标 字符 next[i]
0 a -1
1 b 0
2 a 0
3 a 1
4 b 1
5 c 2
6 a 0
7 c 1
对于next[0]与next[1]，无意义
next[2]，看前两个字符ab，前1与后1不同，故取0。
next[3]，对于aba，前1与后1相同，但取长度2就不同了，故next[3]=1。
以此类推，手算的话，就是枚举i-2~0的长度值，截取前缀串进行比较。
楼主所说的next[6]=3是不是算错了。。。- -