【6.C++基础】-算法-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移动到此处。结束