书接上回。
发现中考英语作文没拿满分，严肃意识到自己不会字符串。
由于现在是上午，所以只学一个算法，剩下一个放在下午。 都快打 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 )。
P2322
Difficulty：4.6 / Easy
Tag：ACAM
定义 dis[cur][mask]dis[cur][mask]dis[cur][mask] 为当前匹配状态为 curcurcur 与总共匹配了串有 maskmaskmask 的最短距离，ACAM 套个广搜，最后反着找路径即可。
咦怎么还卡空间。
时间复杂度：O(2n∣S∣∣Σ∣)O(2^n|S||\Sigma|)O(2n∣S∣∣Σ∣)。
空间复杂度：O(2n∣S∣)O(2^n|S|)O(2n∣S∣)。
后缀数组
显然 sort + 哈希二分比较大小可以做到 O(nlog2n)O(n\log^2 n)O(nlog2n)，但我现在才 16 岁，16 岁用双模哈希，32 岁就用四模哈希，64 岁就用八模哈希了，我不得成八常大数了？而且有 O(nlogn)O(n\log n)O(nlogn) 做法我为啥不写/续标识
考虑倍增。我们通过每个位置后 2i−12^{i-1}2i−1 个字符的串的排名拼接得到 2i2^i2i 个字符的排名，然后离散化一下。
如果直接 sort 的话还是 O(nlog2n)O(n\log^2 n)O(nlog2n) 的，但是我们注意到每次倍增的值域只有 n2n^2n2，所以神秘两次基排就可以 O(nlogn)O(n\log n)O(nlogn) 了。
这时你可能要问了，卧槽你这常数不得大飞啊。
没事，注意到我们在上一轮基排时其实已经求出了低位的排名了，所以通过上一次的排名，我们就可以将两次基排优化成 1.1 次基排。常数大大减小了（喜）
突然发现不会桶排，照着 OI-wiki 抄的，啥意思其实不知道（
然后这玩意可以求一个叫做 height 的东西，定义如下：
height(i)=LCP(A[sai,n],A[sai−1,n])\text{height}(i)=\text{LCP}(A_{[\text{sa}_i,n]},A_{[\text{sa}_{i-1},n]})height(i)=LCP(A[sai ,n] ,A[sai−1 ,n] )。
这个有两个性质：
* height(ranki)≥height(ranki−1)−1\text{height}(\text{rank}_i)\ge\text{height}(\text{rank}_{i-1})-1height(ranki )≥height(ranki−1 )−1
* LCP(A[i,n],A[j,n])=∑k=ranki+1rankjheight(k)\text{LCP}(A_{[i,n]},A_{[j,n]})=\sum_{k=\text{rank}_i+1}^{\text{rank}_j}\text{height}(k)LCP(A[i,n] ,A[j,n] )=∑k=ranki +1rankj height(k)
前者可以让你 O(n)O(n)O(n) 递推求出 height，后者可以让你以 RMQ 的方式 O(1)O(1)O(1) 计算一个串任意两个后缀最长公共前缀。
P3181
求公共子串个数。
A=S1+{+S2A=S_1+\{+S_2A=S1 +{+S2 ，跑一遍 SA，然后转化成了求 ∑i=1n∑j=i+1n([sai<∣S1∣+1]⊕[saj<∣S1∣+1])mink=i+1jheight(k)\sum_{i=1}^n\sum_{j=i+1}^n([\text{sa}_i\lt |S_1|+1]\oplus[\text{sa}_j\lt |S_1|+1])\min_{k=i+1}^j \text{height}(k)∑i=1n ∑j=i+1n ([sai <∣S1 ∣+1]⊕[saj <∣S1 ∣+1])mink=i+1j height(k)。
那咋办？
