kmp
经典字符串匹配算法。其实是通过找本身前缀\(i\)的最长border，来实现快速匹配的。
这里给出border的定义：字符串\(s\) 的一个子串既是它的前缀又是它的后缀，则这个子串是它的border（一般不包含本身）
kmp通过fail在border上跳，使得每次前面部分的字符串都是相同的，判断新加入的是否匹配即可。
void getkmp(char* s, int n) {
int p = 0;
fail[1] = 0;
for (int i = 2; i <= n; i++) {
while (p && s[i] != s[p + 1])p = fail[p];
if (s[i] == s[p + 1])p++;
fail[i] = p;
}
}
例题：
luogu: P3375 【模板】KMP
luogu: P4696 [CEOI2011] Matching
这题在线段树&哈希也提到过。这里重新定义kmp的相等，可以实现线性复杂度。
fail树/失配树
注意到kmp的fail数组构成了一个一个树形结构。这个就是失配树。失配树上的所有父亲就是这个前缀的所有border。
P5829 【模板】失配树 中问，字符串\(s\)的\(p\)前缀和\(q\)前缀的最长公共border。即找这个两个节点的\(LCA\)(最近公共祖先)
border
性质（这里的border的起点都指开头）：
- 如果有一个border \(k\)长度大于\(s\)的一半，可以得出得\(s\)有周期 \(|s|−|k|\)
- 如果 \(p，q\) 都为周期，则 \(gcd(p，q)\)也为周期
感性理解即可 - 字符串\(s\)所有不小于\(|s|\)一半的border构成一个等差数列
\(|s|−|k|\) 是一个周期，每次减少一个周期都是一个新的border。 - 可以把字符串分成\(log|s|\)段，每一段的border都是一个等差数列
考虑最后一部分等差数列去掉，\(s\)变成左边一半。这一半的border也成等差数列。最多划分成\(log|s|\)段
重新考虑字符串\(s\)的\(p\)前缀和\(q\)前缀的最长公共border。这次我们直接找到border等差数列的开头。也可以在\(O(nlogn)\)时间复杂度内解决。
例题：
luogu: P5829 【模板】失配树
luogu: P4156 [WC2016] 论战捆竹竿
2021ICPC沈阳站M