书接上回。
发现中考英语作文没拿满分，严肃意识到自己不会字符串。
由于现在是上午，所以只学一个算法，剩下一个放在下午。 都快打 CF 了我还没学我怎么这么区。 第二天下午也是下午。 ACAM 我好像学过了，那我就是区。
MANACHER
将每个字符两边用一个滚木包裹，使得所有回文串长度都为奇数。
考虑维护此时每个 iii 为中心的最长回文子串端点与 iii 的距离 PiP_iPi 。则原串答案显然为 (2Pi+1)−12=Pi\frac{(2P_i+1)-1}{2}=P_i2(2Pi +1)−1 =Pi 。
考虑维护目前小于 iii 为中心的最长回文子串中右端点最大值 rrr 及其中心 midmidmid。
由回文串定义（关于中心对称）得，iii 为中心，min{r,i+Pmid−(i−mid)}\min\{r,i+P_{mid-(i-mid)}\}min{r,i+Pmid−(i−mid) } 为右端点的串一定回文。
然后暴力扩展，更新 midmidmid 与 rrr。每次暴力扩展一定会使 rrr 移动 111，而 rrr 一共只会移动 nnn 次，所以时间复杂度为 O(n)O(n)O(n)。
时间复杂度：O(n)O(n)O(n)。
ACAM
学过了，但还是讲一下。
等一下，我真的会吗。
不管了，这个背个板子就行了，然后知道一个点表示一种匹配状态就行了。
时间复杂度：O(∑∣S∣∣Σ∣+∣T∣)O(\sum |S||\Sigma|+|T|)O(∑∣S∣∣Σ∣+∣T∣)
P2292
Difficulty：4.6 / Easy
Tag：ACAM
考虑 DP。dpidp_idpi 表示前 iii 个字符是否可以完全匹配。则有 dpi=ort[i∼j]=Ak{dpj}dp_i=\text{or}_{t_{[i\sim j]}=A_k}\{dp_{j}\}dpi =ort[i∼j] =Ak {dpj }。使用 AC 自动机判断是否完全匹配，这么转移复杂度是 O(nm∣T∣)O(nm|T|)O(nm∣T∣) 的。注意到可以压位记录每个节点匹配状态以及当前最后 ∣S∣|S|∣S∣ 项 dpdpdp 值，然后直接取或即可知道是否有符合条件，优化至 O(m∣T∣)O(m|T|)O(m∣T∣)。理论上如果 ∣S∣|S|∣S∣ 足够大，这个可以用
bitset 做到 O(m∣S∣∣T∣w)O(\frac{m|S||T|}{w})O(wm∣S∣∣T∣ )。
时间复杂度：O(n∣S∣∣Σ∣+m∣T∣)O(n|S||\Sigma|+m|T|)O(n∣S∣∣Σ∣+m∣T∣)。
ABC458F
这个在 https://www.acgo.cn/discuss/rest/77714 Week 7 最后一题口胡过了。
只不过当时我可能没意识到在建 fail 时已经可以预处理能不能到那个点了。
哦好像意识到了，但是反正复杂度瓶颈主要是 O((n∣S∣)3logn)O((n|S|)^3\log n)O((n∣S∣)3logn)，优不优化无所谓。
这是我今天写的第四个 AC 自动机，我感觉再写下去我得成写 AC 自动机 自动机了。
跑得还挺快的，只用了 86ms。
时间复杂度：O((n∣S∣)3logn)O((n|S|)^3\log n)O((n∣S∣)3logn)。
P14363
Difficulty：4.5 / Easy
Tag：ACAM
三周目。真是一对苦命鸳鸯啊。
这就是让我挂 20pts 的下场。
记前缀、S1S_1S1 中间、S2S_2S2 中间、后缀分别为 A,B,C,DA,B,C,DA,B,C,D，则可以转化成 A{BC{DA\{BC\{DA{BC{D。
注意到一个文本串最多只能在模式串种被匹配一次。
所以直接求出 P5357 中 ∑ansi\sum ans_i∑ansi 即可。这个可以递推 O(∣T∣)O(|T|)O(∣T∣) 求出。
时间复杂度：O(L1∣Σ∣+L2)O(L_1|\Sigma|+L_2)O(L1 ∣Σ∣+L2 )。
