KMP算法中的next数组解释
博主说几个重要的理解点，便于各位朋友理解next数组
解惑next数组的求解
一、先理解前缀后缀
如：abcdef
前缀为：a,ab,abc,abcd,abcde 含头不含尾。
后缀为：bcdef,cdef,def,ef,f 含尾不含头。
二、子串
如：abcdef
子串为 a,ab,abc,abcd,abcde,abcedf
从左到右。
三、举例
模式串：P = abctabcabctabct
P所代表的字符串数组，总计15个字符，数组下标 0 ~ 14.
重要点：前后缀的匹配需理解为 对称匹配。
Q：求P的next数组
我们先通过案例找一下规律。
问题：已知P[13] 对应的 next值，即next[13] = 7，求 p[14]所对应的next值，即求next[14]
首先记住一点，对称性。即 ① 和 ②对称。
其次记住，数组下标 0~ 14
最后记住一点，P[14] 的最大元素最多比p[13]多一个，因为P[13] 对应的next值为 7 ，所以 p[14] 对应的next值 最大为8，这条一定要好好理解。
那么对于 p[14] 和 p[13] 的前缀后缀来说，已知 ① = ②，那么 ④相当于 ②后面加个字符“t”（P[14]），那么与此同时，③相对于①来说，也应该增加一位。即①后面加个字符“a”（P[7]）
即最后 ③ 与 ④比较 等价于
①+P[7] 与 ②+P[14] 做比较，① = ② 那么就是 P[7] 与P[14]比较，这里的 数字 7 是什么，是 P[13]对应的next值。
这里是重要的一个知识点，大家多画一下自己理解一下。
其实也很好理解，在P[13]时候 ① = ②，那么当 ②后面增加一个字符后，①也得增加一个字符，然后再比较。那这时候 就是看 ①增加的字符和 ②增加的字符是不是相等。
那么就可以知道。 对于 p[14] 所对应的next值来说，先判断 p[14] 与 p[next[13]] 的关系，也就是p[14] 和 p[7] 的关系。
如果相等，那么 next[14] = next[13] + 1
如果不相等。那么进行下一步。
重要：重要：重要：
我们可以看到 p[14] != p[7] 这时候应该怎么办？
首先：先记住 ① = ②
其次：①这个字符串，我们之前对其进行过前后缀的求值
①中 ⑤等于⑥。 ②中⑦等于⑧。① = ②。
可以推算出 ⑤ = ⑧
这里有小伙伴会问为什么写 ⑤等于⑧
大家想一想，对于P[14] 得出的next值是什么，是前缀和后缀获得。
⑧+第14位字符“t” 和 ⑤+第3位字符“t” 是不是一个P[14]是后缀 一个是 P[14]的前缀
那么就相当于比较 P[14] 字符 和 P[3] 字符是否相等。这里的 3 是什么，是 P[7 - 1] 所对应的next值
这时候大家再对照一下代码，我写一下伪代码
1、先得到 next[13] 的值，变量 K 代替，即 K = next[13] = 7
2、判断 P[14] 和 P[K]（即P[7]）是否相等
3、如果相等，则next[14] = next[13]+ 1;如果不相等那么 这时候 K = next[K - 1] 即 K = next[7 - 1] = next[6] = 3
4、判断P[14] 和 P[K]（即P[3]） 是否相等
5、相等 next[14] = next[6] + 1 = 4
OK 我们这时候从头开始推算
| a | b | c | t | a | b | c | a | b | c | t | a | b | c | t |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
K = 0
1、next[0] = 0；
2、next[1]，判断P[1] 和 P[K]的关系，即P[1] 和P[0]，不相等，这时候 K = next[K - 1] = next[-1] 这种情况不应该出现，所以会需要有判断K 与 0 的关系。暂时不表。结果： next[1] = K = 0
3、next[2]，判断P[2] 和 P[K] 的关系，即P[2] 和 P[0]，不相等。结论 next[2] = K = 0
4、next[3]，判断P[3] 和 P[K] 的关系，即P[2] 和 P[0]，不相等。结论 next[3] = K = 0
5、next[4]，判断P[4] 和 P[K] 的关系，即P[4] 和 P[0]，相等。结论 next[4] = K + 1 = 1 ；同时 K = K + 1 = 1
6、next[5]，判断P[5] 和 P[K] 的关系，即P[5] 和 P[1]，相等。結論 next[5] = K + 1 = 2；同時 K = K+ 1 = 2；
。
。
。
7、next[14]，判断P[14] 与 P[K] 的关系，即P[14] 和 P[7]，不相等，这时候 K = next[K - 1] = next[6] = 3，判断P[14] 和 P[K]的关系，即P[14] 和 P[3]，相等，next[14] = K + 1 = 3 + 1 = 4