KMP再次总结

为何连算法都会总忘记 =。= 反省，脑袋有包
关键点：target 串（长的），partten 串，如果二者在 j 上不等，将 partten 可以向前移动 next[j]而取代只前移 1
如何确定 next[j]? T 与 P 在 j - 1 前都相等，所以若移动后想要相等，移动后的前面部分也要与这部分 T 相等，三者相等：
T[j-k~j]=P[j-k~j]=P[1~K]，否则移动都是冗余的 即转为短串 P 的重复问题。
先看看如何找到子串的冗余 f(i)的长度。因为都是与 1 比，很简单：若 i 之前的都相等，第 i 个也相等，则加 1，否则是 1，再继续

   a    b    c    a    b    c    a    c    a    b
   1    1    1    2    3    4    5    1    2    3

因为我们要求的是不匹配的，每次计算都是前一个，向右移一下

   0    1    1    1    2    3    4    5    1    2

所以若要匹配，可以至少移动到 k 与不匹配的值比较（k-fi 步）。进一步 若 T 与 P 移动后的 p[k]相等，我们知道,k 前面与 Tj 前面是相等的，但 p[k]!=t[j]则肯定不匹配，与刚移动前情况一样，递归移动到两个值不等或开头即可，否则也都不匹配就没有意义
常规：

   a    b    c    a    b    c    a    d    a    b
   a    b    c    a    b    c    a    c    a    b
                  a    b    c    a    b    c    a    c    a    b

更进一步, 最后前的两部可以省略：

   a    b    c    a    b    c    a    b    a    b
   a    b    c    a    b    c    a    c    a    b
                a    b    c    a    b    c    a    c    a    b
                            a    b    c    a    b    c    a    c    a    b
                                a    b    c    a    b    c    a    c    a    b

因此移动的 nextk（在 j 处不匹配每次可以将下标为 nextj 的移动到不匹配的 Tj 上进行过匹配）为：
如果 pattern[j] != pattern[f(j)]，next[j] = f(j);
如果 pattern[j] = pattern[f(j)]，next[j] = next[f(j)];

第一次 j =1，将 0 移动到此处
第二次 j =4, 将 0 移动到此处
第三次 j =8, 将 5 移动到此处
第四次 j =5，将 1 移动到此处
第五次 j =8, 将 5 移动到此处。结束