KMP真是记一次忘一次。归根到底，还是没有彻底理解。

为了彻底理解，我们这次来画个图。

理解KMP，最关键的是理解next数组。

next数组是基于需要匹配的字符串的一个数组。

如有字符串target，

我们定义next(i) 为，字符串target[0:i+1]的最长的相同前缀与后缀的长度。

什么叫字符串的前缀？

字符串的前缀就是下标从0开始，连续的不包括最后一个下标的子串。
比如abcd的前缀有a,ab,abc。
同理，字符串的后缀就是包括最后一个下标，不包括第一个下标的连续子串。
所以abcd的后缀有b,bc,bcd。

如何判断最长的相同前缀后缀？

举个例子， target='aabaaba',
当i=0的时候，因为一个字符不存在所谓前缀后缀，我们规定next[0] = 0
当i=1的时候，前缀有a，后缀有a有前缀a等于后缀a。所以next[1]=1。
当i=2的时候，前缀有a，aa，后缀有ab，b，但是没有一个是相同的，所以next[2]=0
当i=5的时候，有前缀aab等于后缀aab。所以next[5]=3。
当i=6的时候，有前缀aaba等于后缀aaba。所以next[6]=4。

我们这里写一个算法。

1
2
3
4
5
6
7
8
9
10

# 假设字符串为niddle, 这里用dp表示next数组。

dp = [0] * len(needle)
j = 0
for i in range(1, len(needle)):
    while (j > 0 and needle[j] != needle[i]):
        j = dp[j-1]
    if needle[i]  == needle[j]:
        j+=1
    dp[i] = j

这个怎么理解？

我们把j放在niddle的0下标处，开始遍历niddle。当前下标为i。 这里的j就可以看成当前的最长前缀后缀长度。

当niddle[i] == niddle[j], 最长前后缀长度加1，继续比较下一个i。

若niddle[j] != niddle[i]， 我们得把j回溯到一个位置k，使得niddle[0:k] 和从niddle[i-1-k:i]相同。这样我们可以直接继续比较j和i。

那么这个k等于多少呢？ 这个k是dp[j-1]。

为什么？ 因为我们知道niddle[:j] 和 niddle[i-1-j:i] 相同， 而 niddle[j-1-k:j] 和 niddle[0:k] 相同。那么必然，niddle[0:k] 也和niddle[i-1-k:i]相同。

这里说得太抽象了，画个图解释一下。

蓝色部分的长度就是k，红色部分的长度就是一开始的j了。

当我们把j移动到k处，继续比较新的j和i，如果还是不一样，自然我们得继续缩小k了。

注意有个细节是不匹配的时候我们把j移动到dp[j-1]，这个时候其实相同的前后缀部分是niddle[:dp[j-1]]，因为dp的定义是长度！

至此，kmp的next数组的生成方式应该是理解了。