KMP 第 114514 遍重新学。
这个算法的作用求出前缀函数 \(\pi\)，一种应用才是字符串匹配。
真前缀：是前缀但不是其本身，即最长为 \(s[1 \dots n-1]\)。
前缀函数：一般地，前缀函数 \(\pi[i]\) 表示子串 \(s[0\dots i]\) 最长的相等的真前缀与真后缀的长度，代码中我们一般写作 \(nxt[i]\)。
前缀函数的求法：自己和自己做匹配，全文背诵。
理解去 B 栈搜天勤考研讲的《KMP 易懂版》，确实易懂。
// lb 是字符串 b 的长度
for (int i = 2, j = 0; i <= lb; i++)
{
while (j && b[i] != b[j + 1])
j = nxt[j];
if (b[i] == b[j + 1])
j++;
nxt[i] = j;
}
P3375 【模板】KMP
在求出 \(nxt[]\) 的基础上，我们就可以跳跃着比较两个字符串了，时间复杂度是 \(O(n+m)\) 的。
P4391 [BOI2009] Radio Transmission 无线传输
瞪眼法发现答案是 \(n-nxt[n]\)。
简单说就是比较把最长公共前缀和后缀叠在一起时：
可以循环判定 \(s_{红}=s_1=s_2=s_3=s_4=\dots\)
故红色段为循环节。
让红色尽量短就是让最长公共前后缀尽量长。
CF25E Test
几乎是模拟了。
枚举全排列然后判断中间的公共部分删掉。
注意考虑包含的情况。
P3435 [POI2006] OKR-Periods of Words
好题。
一个 proper 前缀 就是真前缀。
一个 周期 就是满足以下条件的子串。
-
是原串的前缀。
-
叠两遍后原串是它的前缀。
参考示例：
我们发现这个原串满足前缀 = 后缀。为了让周期（第一行红）最大，我们只需让公共前后缀最小。
于是求出 \(nxt[]\) 后，有了一个暴力做法：
for (int i = 2; i <= n; i++)
{
int x = i;
while (nxt[x])
x = nxt[x];
ans += i - x;
}
每次让 \(x\) 往回跳找到非零的 \(nxt\)。
复杂度 \(O(很慢)\)，原因是 x 要回溯。
注意到我们会有多次跳到同一个 \(x\)，而每次都要重复计算 \(x\leftarrow nxt[x]\)，可以让 \(nxt\) 直接存储最终情况，这样每次至多回溯一次。
for (int i = 2; i <= n; i++)
{
int x = i;
while (nxt[x])
x = nxt[x];
if (nxt[i])
nxt[i] = x;
ans += i - x;
}
时间复杂度 \(O(n)\)。
P2375 [NOI2014] 动物园
就是求出 \(num[i]\) 表示不重叠的最大公共前后缀长度。
马上有一个回溯的算法，求出 \(nxt[]\) 后回溯 \(nxt[i] \leftarrow nxt[nxt[i]]\)。
但这只能过 50pts，考虑优化。
单步跳太慢了，我们可以用倍增优化。
普通的倍增可以过 80pts，但可以通过卡 cache 搞过。
只需要把倍增的第一维放小的，第二维放大的，这样内存访问连续很多，效率大大提升。
这提醒我们在多次连续跳跃查询的时候，倍增是一种常用优化策略。如树上倍增。
龚老师只会 \(O(n^2)\) 解法，提问未遂。
P4824 [USACO15FEB] Censoring S
巧妙。
看见字符串匹配，考虑 KMP。
在生成答案的过程中，可以理解为依次加入后发现有重复就删掉，让人想到栈。
于是用一个栈记录所有保留的字符，一边加入栈一边做 KMP，当发现匹配成功就弹出一整个 \(b\) 串，同时匹配指针回到加入这个 \(b\) 串之前的状态，这也可以在做 KMP 的时候处理。
我们发现这种情况下，栈一次要弹出很多元素，此时数组模拟是优于 STL 的选择。
P3426 [POI2005] SZA-Template
70pts
注意到字符串若能被一个印章覆盖，这个字符串一定前缀等于后缀。自然想到用 KMP 求出最长公共前后缀。
对于覆盖的判断，可以用 DP 解决。具体地，用 \(f[i]=0/1\) 表示该位置可以被覆盖到。则匹配完就可以把长度为当前串的 \(f\) 置为真。因为涉及区间操作，可以用数据结构优化。这里我使用了常数较小的树状数组进行区间加单点查。
90pts
发现用树状数组优化 DP 实在太蠢，字符串哈希可以承担这个工作，改成字符串哈希即可。
100pts
一个小优化：当左端点已经超过了覆盖区域的右端点时，再进行判断已经无意义了，直接 break。
注意：特判没有公共前后缀可以让整段被覆盖时，最小的印章就是其本身。
听说还有 \(O(n)\) 做法，过于精妙看不懂。
标签：nxt,前缀,后缀,可以,KMP,字符串 From： https://www.cnblogs.com/tai-chi/p/18340978