前言
我今天生日！！！
由来
KMP 算法，是由 Knuth、Pratt 和 Morris 三位巨佬发布的一个算法。
他可以在线性（说人话就是 \(O(n + m)\) ）时间复杂度内在字符串中查找子串。
思想
朴素算法：
枚举每一个元素，然后从这一位开始不断向后比较，每次比较失败之后都要从上一次匹配的位置的下一个位置开始重新比对，最好时间复杂度是 \(O(n+m)\) 的，但是如果子串比较靠后或者匹配失败比较多，最坏可以卡到 \(O(nm)\) 的。
字符串哈希
朴素算法的慢，是因为判定子串和截取的原串的时间复杂度是 \(O(m)\) 的，有不有什么方法可以使判断子串的时间复杂度变成 \(O(1)\) 呢？
我知道，字符串哈希。
预处理出哈希表，之后再查一查就好了。
时间复杂度：\(O(n+m)\)
正确率：\(\ge 95\%\)。（话说 dzl 十哈希被卡了？）
KMP
如果能让指针 \(i\) 不后退，就能让时间复杂度优化成 \(O(n + m)\)。
字串：abcab
原串：abcacababcab
首先看看 \(a[i+1]\) 是否等于 \(b[j + 1]\)，如果是，\(i\) 和 \(j\) 都加 \(1\)。
否则找到一个 \(k\)，使得 \(b[1] \sim b[k] = a[i - k + 1] \sim b[n]\)，跳回 \(k+1\) 这个位置。
依次匹配下去。
next 数组
KMP 的精髓在 \(next\) 数组上。
当 \(a[i] == a[j + 1] \ (1 \le i \le n,0 \le j \le n)\) 时，\(i\) 和 \(j\) 都加 \(1\)。
否则查一查 \(next\) 数组，考虑更小的区间，反复跳回直到可以再次进行操作的位置，这就是 \(next\) 数组的处理法。
历史背景
KMP 算法由 Donald Knuth、James H. Morris和Vaughan Pratt 三位巨佬于 \(1977\) 年联合发明。该算法的名称来源于这三位科学家的姓氏首字母。KMP 算法的发明背景源于当时计算机资源稀缺，特别是在进行大文本字符查找时，响应时间过长，无法充分利用计算资源。
例题
1.[【模板】KMP](P3375 【模板】KMP - 洛谷)
模版题，代码如下：
void init_next(){int j = 0;nxt[1] = 0;for(int i = 2;i <= n;i++){while(j > 0 && b[i] != b[j + 1]){j = nxt[j];}if(b[i] == b[j + 1]) j++;nxt[i] = j;}
}
void solve(){init_next();int i = 0,j = 0;for(;i <= n;i++){while(j > 0 && a[i] != b[j + 1]){j = nxt[j];}if(a[i] == b[j + 1]){j++;}if(j == m){printf("%d\n",i - m + 1);j = nxt[j];}}for(int i = 1;i <= n;i++)printf("%d ",nxt[i]);
}
2.[[BalticOI 2009] Radio Transmission 无线传输]([P4391 BalticOI 2009] Radio Transmission 无线传输 - 洛谷)
思路：求出字符串的 \(next\)，用 \(n - next[n]\)。
证明：从字符串的某一处开始到串末，和串首到某一处是完全相等的，其中最长的就是最长公共前后缀。
所以，答案就为 \(n - next[n]\)。
代码：
void solve(){printf("%d\n",n - next[n]);
}
后记
KMP 难在 \(next\) 数组上，考点也在 \(next\) 数组上，所以，还是好好学习 KMP 吧！（用 find 函数）