kmp是一个模式匹配串，主要作用即给出一个串t，一个串s，问s中是否有子串和串t相等的解法。

暴力时间复杂度则是O(len(t) * len(s))

那么kmp则是在暴力匹配的情况下记录了串的已匹配特征来减少回溯的范围。

1.首先求next数组.

这里预先知道s[1~n], t[1~m]为存储的字符串


next[j]即当s[i]与t[j + 1]不相等时，我们应该回溯到 next[j] 处进行继续匹配。


因为s[i]和t[j + 1]不相等，那么可知s[1 ~ i - 1]和t[1 ~ j]是两者一一对应相等的地方


如果在t[1~j]中存在某前缀等于后缀，（前缀和后缀必须小于1~j的长度）


假设前缀为t[1~x], 后缀为t[y~j]


那么再匹配的时候我们就可以直接把t串往后移y - 1位，那么对应到next数组上，即next[j] = x;
即：再将t[x + 1]与s[i]进行匹配。


所以我们需要预先处理下，当某位不匹配时，其前一位的next[j]等于什么，那么我们可以通过上述得知


每一个next[j]都等于（有相等前缀和后缀时，前缀/后缀的长度）即next[j] = x 或 next[j] = j - y + 1

next数组的具体实现：

m为t串长度, 这里采用双指针来判定前缀是否等于后缀

next[1] = 0;

//i为后缀指针，j为前缀指针。从第2个字符开始遍历
for(int i = 2, j = 0; i <= m; i++){
    
    /*
    当j = 0,说明当前前缀就是t[1]，那么直接将其与i匹配.
    当t[i] != t[j + 1]当两个后缀指针所指字符不相等，
    则j需要回溯到已匹配好的前缀t[1~j]的next[j]，
    进行再次匹配直到两者相等，或者j = 0.
    */
    while(j && t[i] != t[j + 1]) j = ne[j];



    //如果两者相等，那么前缀后缀相等长度加1
    if(t[i] = t[j + 1]) j++;
    


    //这里的i即后缀的最后一个字符位置，j即前缀的最后一个字符位置
    ne[i] = j;
}

2.匹配过程.

匹配从上述说过的
s串从i = 1开始，t串从j = 0开始方便回溯
s串长n，t串长m

for(int i = 1, j = 0; i <= n; i++){

    //s与t不匹配，那么就回溯到next[j]处，比较t[next[j] + 1]和 s[i]是否匹配
    //当j = 0, 即回到了首字符，那么退出回溯
    while(j && s[i] != t[j + 1]) j = next[j];


    //匹配成功，当前匹配已成功部分长度加1
    if(s[i] == t[j + 1]) j++;

    
    //因为j才0开始，那么当j = n时说明前1~n全部匹配成功
    if(j == n){
        //返回s串中成功匹配的首字符位置
        cout << i - n + 1 << endl;
    
        //未必只有一个子串，回溯继续匹配
        j = ne[j];
    }
}

即kmp的全部过程.