KMP 算法解决的是字符串匹配问题，具体来说就是对于字符串 s，我们希望找到它的一个子串 p。
- 暴力匹配：对于
s中的每一个长度为len(p)的子串，我们都与p暴力比较 - KMP：假设在某点
i+1发生了失配，那么说明这个点之前都是匹配的，假设匹配的长度为j，即p[:j] == s[i+1-j:i+1]且p[j] != s[i+1]。那么可以让j回退到上一个能匹配的位置p[:k] == s[i+1-k:i+1]，查看此时能否匹配（p[k] == s[i+1]?），不行的话就继续回退。 - 可以发现
p[j-k:j] == s[i+1-k:i+1]，意思是找k这个过程与s无关，因为p已经匹配了一部分。那么我们就是要找p[j-k:j] == p[:k]，即p[:j]的真前缀和真后缀的最大匹配长度，也就是next[j]。 - 那么怎么维护
next数组呢？假设我们已经计算出了next[:i]，要计算next[i]。设c = next[i-1]，有p[i-c:i] == p[:c]，那么如果p[i] == p[c]，就有p[i-c:i+1] == p[:c+1]，此时next[i] = c + 1。否则回退c，令c = next[c-1]，也就是上一个能匹配的位置，继续比较p[i] == p[c]。若相等，则next[i] = c + 1，否则一直回退到不能回退了，则next[i] = 0