『从入门到入土』串串学习笔记

Hoks · 2024-03-12 20:21:08 · 算法·理论

目录

• 0.前言
• 1.附题单
• 2.KMP
  • 2.1.前缀函数
  • 2.1.1.定义
  • 2.1.2.计算
  • 2.2.KMP 算法
  • 2.2.1.模板
  • 2.2.2.Password 模板+思维
  • 2.2.3.Power Strings 典中典
  • 2.2.4.Writing a Song KMP 转移 dp
  • 2.2.5.Prefix Function Queries KMP 自动机
  • 2.2.6.P9606 [CERC2019] ABB KMP 求最长回文子串
  • 2.2.7.P3426 [POI2005] SZA-Template KMP+dp
  • 2.2.8.P3502 [POI2010] CHO-Hamsters KMP+矩阵优化 dp
  • 2.2.9.P5829 【模板】失配树 KMP+LCA
  • 2.2.10.The Supersonic Rocket 计算几何+KMP
  • 2.3. Border Theory
  • 2.3.1. 结论与证明
  • 2.3.2. P1393 Mivik 的标题 Border Theory 模板运用
  • 2.4.后记
• 3.Hash
  • 3.1.定义
  • 3.2.实现
  • 3.3.应用
  • 3.3.1.P3375 【模板】KMP Hash 不可做
  • 3.3.2.P9606 [CERC2019] ABB 大力 Hash
  • 3.3.3.P3501 [POI2010] ANT-Antisymmetry Hash+二分
  • 3.3.4.P3538 [POI2012] OKR-A Horrible Poem Hash 求最短循环节+质因数分解优化
  • 3.3.5.Matrix Matcher 二维 Hash
  • 3.3.6.P3763 [TJOI2017] DNA 可以失配 k 次的字符串匹配问题
  • 3.3.7.P3449 [POI2006] PAL-Palindromes 美妙结论+Hash
  • 3.3.8.P3546 [POI2012] PRE-Prefixuffix dp+Hash
  • 3.4.后记
• 4.Trie
  • 4.1.定义
  • 4.2.实现
  • 4.3.应用
  • 4.3.1.P4407 [JSOI2009] 电子字典 trie+dfs
  • 4.3.2.P6088 [JSOI2015] 字符串树 可持久化 trie
  • 4.4.后记
• 5.Manacher
  • 5.1.算法思想与实现
  • 5.2.应用
  • 5.2.1.P9606 [CERC2019] ABB Manacher 做法
  • 5.2.2.P4287 [SHOI2011] 双倍回文 Manacher 好题
  • 5.2.3.P6216 回文匹配 Manacher+KMP
  • 5.3.后记
• 6.Z 函数（扩展 KMP）
  • 6.1.算法思想与实现
  • 6.2.应用
  • 6.2.1.P5410 【模板】扩展 KMP/exKMP（Z 函数）
  • 6.2.2.Prefixes and Suffixes 和 Division + LCP (hard version)
  • 6.2.3.P7114 [NOIP2020] 字符串匹配 Z 函数与循环节
• 7.ACAM
  • 7.1.定义
  • 7.2.实现
  • 7.3.应用
  • 7.3.1.[P3966 TJOI2013] 单词 Fail 树板题
  • 7.3.2.P4052 [JSOI2007] 文本生成器 ACAM 上 dp
  • 7.3.3.P2444 [POI2000] 病毒 ACAM+dfs 找环
  • 7.3.4.P2414 [NOI2011] 阿狸的打字机 Fail 树+BIT
  • 7.3.5.Death DBMS ACAM+树剖！
  • 7.3.6.P2336 [SCOI2012] 喵星球上的点名 思路转化+Fail 树+BIT
  • 7.3.7.[GEN - Text Generator] ACAM +矩阵优化 dp
  • 7.3.8.String Set Queries 可持久化 ACAM
  • 7.3.9.Duff is Mad/P7582 「RdOI R2」风雨(rain) 根号相关的 ACAM
  • 7.3.10.[P8571 JRKSJ R6] Dedicatus545 ACAM+虚树
  • 7.4.后记
• 8.SA
  • 8.1.定义
  • 8.2.实现
  • 8.3.SA 与 LCP
  • 8.4.应用
  • 8.4.1.PHRASES 最长不重叠出现子串
  • 8.4.2.P4070 [SDOI2016] 生成魔咒 SA+字符串翻转
  • 8.4.3.P3975 [TJOI2015] 弦论 SA 求第 k 小子串
  • 8.4.4.P3181 [HAOI2016] 找相同字符 SA+单调栈
  • 8.4.5.P3649 [APIO2014] 回文串 SA+Manacher+ST 表

0.前言

• Warning：本篇文章的跨度极大，请量力而行。

写这篇文章的初衷是仿照树剖博客，串联的讲完有关串串的大部分 \mathrm{OI} 中会用到的算法。

因为是 『从入门到入土』，所以，这篇文章将会 \mathrm{Hash，KMP} 开始，讲到 \mathrm{SAM,PAM} 结束。

P.S.：本文中的字符串下标均从 1 开始，有关树的根节点均为 0。

那么，在正式开始前，还是致谢：

• 感谢从各个方面给我帮助的神犇 lzyqwq。
• \mathrm{Hash} 题单中的众多好题正是搬运自 lsj2009 的 \mathrm{Hash} 题单。
• \mathrm{ACAM} 题单的前身便是 abruce 的 \mathrm{ACAM} 题单喵，他详细描述的题单真的非常好。
• \mathrm{manacher} 题单来自于 Shiota_Kaede 喵。
• 感谢旻偲指出 Power Strings 中证明部分的错误。
• 感谢postpone指出 3.3.1 节中错误的做法。

1.附题单

『基础篇』KMP系列

『从入门到入土』哈希

『进阶方法篇』manacher

『进阶方法篇』Z 函数

『提高进阶篇』ACAM

『究极折磨挑战篇』SA,SAM,PAM

如果要收藏的话麻烦收藏原题单喵。

2.\mathrm{KMP}

\mathrm{KMP} 算法用于解决字符串匹配问题，其本质是使用了前缀函数。

所以本块将先介绍前缀函数。

2.1.前缀函数

2.1.1.定义

对于长度为 n 的字符串 s，其前缀函数是一个长度为 n 的数组 \pi。

定义 \pi_i 为子串 s_1\sim s_i 的最长相等真前后缀。

其中后面这个部分，也就是字符串 s 的相等真前后缀，叫做 border。

那么定义 \pi_i 为子串 s_1\sim s_i 的最长 border。

写成数学式子也就是：

特别的，规定 \pi_1=0。

举例而言，对于字符串 syxsyxqwq：

又因为 \pi_i 表示的是子串 s_{1\sim i} 的最长 border，所以 \pi_{\pi_i} 即为其次长 border。

按照这个匹配上退出，失配一直跳的思路，我们便得到了求前缀函数的代码。

void getnxt(char s[],int n,int nxt[])
{
    for(int i=2,j=0;i<=n;i++)
    {
        while(j&&s[i]!=s[j+1]) j=nxt[j];
        if(s[i]==s[j+1]) j++;nxt[i]=j;
    }
}

2.2.\mathrm{KMP} 算法

学会了如何求前缀函数，接着来考虑运用。

\mathrm{KMP} 算法便是前缀函数的一个经典运用。

2.2.1.模板

考虑经典例题 P3375【模板】KMP。

比较简单的是第二问，第二问答案即为 \pi 数组。

接着来考虑第一问。

假设我们已经处理到了文本串 s 的第 i 位，而此时模板串 t 匹配到了第 j 位。

首先考虑如果下一位能匹配上，那就直接匹配。

即为：if(s[i]==t[j+1]) j++;。

那如果不能匹配，考虑失配如何跳转。

因为我们要能匹配上的是最长的，并且在移动模式串后文本串仍能匹配上。

那这是什么呢？

不就是最长的 border 吗。

所以，考虑匹配不上时，跳转到 \pi_j。

匹配部分代码如下：

for(int i=1,j=0;i<=m;i++)
{
    while(j&&s[i]!=t[j+1]) j=nxt[j];
    if(s[i]==t[j+1]) j++;
    if(j==n) print(i-n+1),puts(""),j=nxt[j];
}

其中 nxt 即为 \pi。

附上 std。

2.2.2.Password 模板+思维

这题的简化题意就是：

• 求给定字符串的一个子串，使得这个子串既是前缀，又是后缀，而且在字符串中（非前后缀）出现过。或者输出无解。

首先考虑即是前缀又是后缀，这个非常简单，也就是 border。

接着考虑如何保证这个字符串在中间也出现过。

考虑 \pi_n 表示 s_{1\sim n} 的最长 border 长度，正是 s_{1\sim \pi_n}=s_{(n-\pi_n+1)\sim n}。

而 \pi_i 表示 s_{1\sim i} 的最长 border 长度，也就是 s_{1\sim \pi_i}=s_{(i-\pi_i+1)\sim i}。

那么如果 \pi_n=\pi_i，也就是 s_{(n-\pi_n+1)\sim n}=s_{1\sim \pi_n}=s_{(i-\pi_i+1)\sim i}。

那么在这个连等式中，第一个就是后缀，第二个为前缀，第三个就是中间出现过的了。

也就是，问题被转化为了找到一个 \pi_i=\pi_n。

但是，真的是这样的吗？

我们求的不一定是最长 border 啊，可能是其他的 border，也可以符合题意啊。

那么考虑 \pi_n 能否匹配，如果能那就输出解，否则跳转至 \pi_{\pi_n}。

那这样判断是否有解的话，复杂度也是 n^2 的。

考虑构造一个字符串形如 aaa\dots aaa。

那么 \pi_i=i-1，\pi_n 的跳转次数便会达到 n 次，再加上每次扫一遍 \mathrm{O}(n)，直接 T 飞。

考虑前缀函数的性质：每次至多加 1！

这说明什么？

我们只需要得到 mx=\max\{\pi_i\}，那么一直跳转 \pi_n 直到 \le mx 即可。

因为前缀函数一次至多加 1，所以想要变到 mx 的话，值为 0\sim mx 的 \pi 都存在。

代码也就非常精简了。

附上 std。

2.2.3.Power Strings 典中典

（修正了一些问题，感谢旻偲指出错误。）

简化题意：

• 给定字符串，求最短循环节的循环次数。

这里是一个重要结论，需要掌握证明。

结论即为，循环节当且仅当 (n-\pi_n)\mid n 时存在，且最短循环节为 n-\pi_n。

下面给个证明：

首先这个结论是对 border 成立的，但是不为最短循环节。

也就是对于一个长度为 m 的 border，当且仅当 (n-m)\mid n 时为循环节。

考虑把字符串复制一份对齐原串的 border 结尾，就得到了：

（不是很对齐，见谅。）

其中 border 就是对其的那两段：s_{m+1\sim n},s_{1\sim n-m}。

显然的是上下 s_{1\sim m} 都是相同的，

又因为上下对齐的部分也是相同的（因为是 border）。

所以 s_{1\sim m}=s_{m+1\sim 2\times m}。

类比上面的过程一直循环往前推，就能一直推到 s_{1\sim m}=s_{(k-1)\times m+1\sim k\times m}(k\times m\le n\&(k+1)\times m>n)。

那这样的话，最后字符串还会剩下 s_{k\times m+1\sim n} 或是为空。

如果存在这一段的话，长度 len<m，所以这个 border 便不是循环节。

也就是只有为空的时候才是循环节。

也就是 (n-m)\mid n 时才为循环节。

接着来证明 \pi_n 这个 border 求出来的是最短循环节。

这个就很简单了，因为 \pi_n 是最长的 border，而 border 越长，n-m 就越短，所以求出来的就是最短循环节了。

但这里还有个不严谨的地方，就是如何证明 (n-\pi_n)\nmid n 时 ，肯定没有更长的循环节。

考虑反证法，假设有更长的循环节（长度为 k）能满足条件，而 n-\pi_n 不能满足条件。

递推一下就可以得到 s_{\pi_n+1\sim k}=s_{n-k+1\sim n-\pi_n}。

也就是这个长度为 k 的循环节也是个 border，且长度 k>\pi_n。

类似于上图的做法，考虑对其一下，就能得到：

可能最小段+附加段=附加段+可能最小段。

那么这个段就是可以继续找到循环节分割的。

分割后的串长度肯定是小于等于最小可能段长的。

如果分割出的段和最小可能段一样，那么根据题设是不行的。

如果分割出的段比最小可能段还小的话，和最小可能段的定义矛盾了，也是不行的。

也就是当 (n-\pi_n)\nmid n 时，不存在长度 <n 的循环节。

（这一段一定要好好理解再自己证明一遍！）

附上 std。

\LARGE{练习题}

P4391 [BOI2009] Radio Transmission

这道题和上面那道题基本没有区别。

附上 std。

P3435 [POI2006] OKR-Periods of Words

略微提升一二的题目。

附上 std。

2.2.4.Writing a Song \mathrm{KMP} 转移 \mathrm{dp}

简要题意：

• 给定长度为 n 的字符串 t，构造一个字符串 s，使得在给定位置出现/不出现字符串 t。

考虑设计一个 \mathrm{dp}：

Extend to Palindrome

EPALIN - Extend to Palindrome

这两题都是经验了，输出方案的话随便改改上面那题就过了。

2.2.7.P3426 [POI2005] SZA-Template \mathrm{KMP}+\mathrm{dp}

简要题意：

• 给定一个长度为 n 的字符串 s，求最短需要多长的一个字符串 t 才能将 s 完全覆盖。

虽然同是 \mathrm{KMP}+\mathrm{dp}，这题的难度可比前面那题高多了。

首先前缀函数 \pi 肯定是得先弄出来的，接着考虑怎么 \mathrm{dp}。

设计一个 \mathrm{dp}：f_i 表示长度为 i 的前缀的答案，那最后的答案即为 f_n。

接着来考虑怎么转移，不难发现 f_i 只可能有两种取值 i,f_{\pi_i}。

因为如果能用一个长度更短的字符串反复覆盖成 s，至少要能覆盖它的最长 border。

考虑下什么时候 f_i=f_{\pi_i}。

那必然是在 i-\pi_i\sim i 存在一个 j 使得 \pi_j=\pi_i。

具体实现用个桶即可。

然后就可以得到超短的核心代码：

for(int i=2;i<=n;i++) f[i]=(h[f[nxt[i]]]>=i-nxt[i])?f[nxt[i]]:i,h[f[i]]=i;

剩下部分代码好像没必要放了。

2.2.8.P3502 [POI2010] CHO-Hamsters \mathrm{KMP}+矩阵优化~\mathrm{dp}

简要题意：

• 给出 n 个互不包含的字符串，要求你求出一个最短的字符串 S，使得这 n 个字符串在 S 中总共至少出现 m 次，问 S 最短是多少。

考虑 dp。

设计 f_{i,j} 表示填了 j 个串，结尾第是 i 个串的最短长度。

那么转移即为：

其中 w(k,i) 表示在 k 这个字符串后接 i 要多接多少字母。

那么 w(k,i) 的计算就非常一眼了，即为 i 的长度减去 k 的尾部和 i 的头部重复的字母数。

后面这个部分可以直接对字符串跑 KMP 算出来。

这样我们就得到了一个 O(n^2m) 的做法。

发现 m 很大，考虑用矩阵优化递推优化到 O(n^2\log m)。

不难发现，如果我们把每个字符串看做一个点，字符串拼接看做是点间的边。

那么这个题就相当于是在一张 n 个点的图上走 m 步，问最短路长度。

这个就显然是可以用矩阵来做的，矩阵乘法一次就相当于是做了一遍 floyd，所以乘个 m 次快速幂优化下就行。

附上 std。

P3193 [HNOI2008] GT考试 \mathrm{KMP}+矩阵优化~\mathrm{dp}。

P1393 Mivik 的标题 上一道题的再升级加强。

突然发现题目编号好相似。

2.2.9.P5829 【模板】失配树 \mathrm{KMP}+\mathrm{LCA}

简要题意：

• 给定长度为 n 的字符串 s，m 次询问，每次询问查询 s 两个前缀的最长公共 border。

考虑 \mathrm{KMP}，通过跳两个前缀的 \pi 求得所有 border。

思考一下这玩意像什么？

如果把一个字符串看做一个点的话，这个跳 \pi 的过程就是在树上跳。

而求最长公共 border 不就是找两条往上跳的路径的第一个交点吗？

这玩意在树上叫啥来着？

这不就 \mathrm{LCA} 吗。

所以考虑对着 \pi 建出 \mathrm{Fail} 树，在 \mathrm{Fail} 树上求 \mathrm{LCA} 就行了。

其实我个人是更偏向于树剖的，不过代码是以前的代码，就用倍增了。

附上远古抽象马蜂的 std。

XYD 的 2023 年 CSP-S 的模拟赛的 T4 挺好的。

P2375 [NOI2014] 动物园 貌似是纯板子？

2.2.10.The Supersonic Rocket 计算几何+\mathrm{KMP}

简要题意：

• 平面上给定两个点集，判定两个点集分别形成的凸多边形能否通过旋转、平移重合。
• 点集大小 n\le 10^5，值域 [0,10^8]。

题意里都直接给计算几何摆出来也是够抽象的。

那没办法了，先计算几何吧。

不会的自行跳转：P2742 [USACO5.1] 圈奶牛Fencing the Cows /【模板】二维凸包。

个人感觉学个 Andrew 应该够了。

然后题意变成了判断两个凸包是否同构。

此时我们就要进行条件的转化。

如何把一个二维的图形等价为一个一维的信息？

我们考虑全等。

两个凸包在什么条件下是全等的？

边和夹角都相等。

那如何把这东西表示出来呢？

这时我们想到万能的向量。

使用点积表示出夹角就行了（注意不能使用叉积）。

对于整个凸包我们依次存下来边长和夹角绕一圈就行了。

因为凸包是可以转圈的，所以我们的这个序列也是一个环状的。

现在就变成了判断两个字符串是否循环同构了。

考虑直接 KMP 即可。

唯一需要注意的点就是当心角度搞出来 nan 了，记得判下改为 eps 即可。

代码可以见 CF1017E 解题报告喵。

P3454 [POI2007] OSI-Axes of Symmetry

求对称轴数，这里的夹角就可以用叉积规避掉 nan 了喵。

2.3. \mathrm{Border~Theory}

其实 \mathrm{Border~Theory} 就是一些关于 border 的强结论，但是用出来太牛了，所以单独开了一个部分。

2.3.1. 结论与证明

首先介绍什么是 \mathrm{Border~Theory}。

定理 0：如果 i 是 s 的一个 border，那么 |s|-i 是 s 的一个周期。

这个证明就是前面那个 Power Strings，不再赘述。

定理 1（弱周期定理，Weak Periodicity Lemma，WPL）： 若 i,j 都是 s 的一个周期，且 i+j\le|s|，则 \gcd(i,j) 也是 s 的一个周期。

这个证明是简单的。

我们考虑把这个划分的图画出来。

那么就可以发现如果我们把上下两部分作差，中间差出来的那个部分也是一个周期。

也就是对于任意的 k>0，只要满足 ix-jy=k 有整数解，则能取到是一个周期。

由裴蜀定理我们知道 k 肯定是 \gcd(i,j) 的倍数，最小值也就是 \gcd(i,j)。

在此之上还有推论（强周期定理，Periodicity Lemma，PL）：若 i,j 都是 s 的一个周期，且 i+j-\gcd(i,j)\le|s|，则 \gcd(i,j) 也是 s 的一个周期。

定理 2：对于 s 的所有长度 len\ge \lfloor\frac{|s|}{2}\rfloor 的 border，它们与 |s| 构成一个等差数列：

我们不妨先设 s 的两个 border~x,y 满足 len\ge \lfloor\frac{|s|}{2}\rfloor。

由定理 0，我们可知 |s|-x,|s|-y 是 s 的两个周期。

然后因为 x,y 满足 len\ge \lfloor\frac{|s|}{2}\rfloor，所以我们可以根据定理 1 得到 d=\gcd(n-x,n-y) 是 s 的周期。

那么显然的是 d,2d,3d,\dots 都是 s 的周期，所以 |s|-d,|s|-2d,|s|-3d,\dots 都是 s 的 border。

显然的是这与 |s| 组成了一个公差为 d 的等差数列。

而因为我们知道定理 1 是一个下界，所以不可能存在其他长度的 border 满足上述限制。

证毕！

定理 3：将所有 border 按其二进制最高位进行分段，每一段内的 border 都构成一个等差数列。

证明类似于定理 2。

对于最高位由定理 2 我们知道是对的。

接着我们对一个长度段 [2^{i-1},2^i],2^i\le |s| 证明。

假设他有个最长 border 为 t，那么由定理 2 我们知道 t 与 2^i 和剩下的所有 border 形成了一个等差数列，公差为 2^i-t。

那么结合下前面最高位是对的，也就证明完了定理 3

也就是说，对于一个字符串 s，其所有 border 构成 O(\log |s|) 个等差数列。

这就是非常美妙的性质了，意味着如果我们可以一次维护一个等差数列就可以把维护所有 border 的复杂度变对。

通过定理 3 我们还能证明出一个推论：对于一个串 s，所有公差 \ge d 的等差数列个数 \le\lfloor\frac{|s|}{d}\rfloor。

2.3.2. P1393 Mivik 的标题 \mathrm{Border~Theory} 模板运用

简要题意：

• 在一个有 m 个不同按键的键盘上随机打 n 个字符，问产生的字符串包含字符串 S 的概率。

可以见题解喵。

暴力的想法，可以直接上矩阵，思路直接像 GT 考试一样写，那么复杂度是 O(|s|^3n) 显然爆飞了。

可以很容易发现这题的重点肯定是在 n 上了，比起 GT 考试小了许多。

直接上来考虑设计 dp。

我们设 f_i 表示 [i-|s|+1,i] 恰好为 s 且这是 s 第一次出现。

那么我们知道答案是 \sum\limits_{i=|s|}^n f_i\cdot m^{n-i}。

接着就是计算 f_i 了，不难发现，我们先固定 [i-|s|+1,i]，那么剩下的部分直接乱填，方案数是 m^{n-i-|s|}。

接着考虑来去重。

1. 这样的出现显然是完整和目前新造这段不重的。 方案数也很好数，即为 $\sum\limits_{j=0}^{i-|s|}f_j\cdot m^{i-|s|-j}$。
2. 这样就是前面的一段拼上 $s$ 的一段前缀成了一个新的 $s$。 那这个前缀肯定是 $s$ 的一个 $border$。 找到所有的 $border~j$ 进行转移就行了。 方案数就是 $\sum\limits_{j} f_{i-|s|+j}$。

这样建模之后我们从 0 开始跑一遍最短路，跑到的 d_i 的意义就是最小的能达到 \bmod x_1\equiv i 的 d_i。

那么对于 d_i\le w-n，对答案的贡献就是 \lfloor\frac{w-n-d_i}{x_1}\rfloor+1，这点计数显然。

但因为 border 数量是 O(n) 的，所以我们图的边数是 O(n^2) 的，跑 dijkstra 的话无法避免遍历边集，无论如何也没法通过。

那只能从 border 的性质下手了。

由前文我们知道 \mathrm{Border~Theory}。

这个定理最为厉害的地方就在于把 border 划分为了 O(\log n) 个等差数列。

考虑把每个等差数列合起来一次做掉来保证复杂度。

那现在我们要做的就是一次加入一个等差数列的长度的边，维护最短路。

如何让加入等差数列的复杂度变对？

考虑到我们成环本质是无意义的，所以我们只要剥环就行了。

假设公差为 d，取当前的首项 x 为模数，那么就会成 \gcd(x,d) 个环，尝试对每个环做。

新的问题就有了，那么就是最短路的源点不确定了，枚举多源肯定完了。

不难发现边权都是正的，所以环上的最小点显然是不会被更新的，以这个为源点左右拓展即可。

具体的，我们考虑用单调队列实现，直接单调队列的 dp 掉一个环就行了。

接着就剩下最后一个问题了，如何更换模数？

对于假设我们要从模数 x 换到 y，数组 f 换到数组 g。

考虑下本身的意义就是在最小能到达取模模出 i 的位置。

显然的我们可以用 f_i 更新 g_{f_i\bmod y}。

但此时注意到，长度为 x 的转移被我们忽略掉了，所以记得再跑一遍补上就行了。

最后的答案计算就和上面一样。

至此我们完成了这道题。

2.4.后记

\mathrm{KMP} 部分到这里就告一段落了，剩下的可以去看看题单练习练习喵。

别问我为什么没有高维的讲解，我不会喵。

3.\mathrm{Hash}

\mathrm{Hash}，永远的神！

\mathrm{Hash} 可以在 \mathrm{O}(1) 的时间判断两个字符串是否相等，因为这个特性，他可以在时间复杂度仅劣 \log(n) 的情况下，从码量和理解难度方面薄纱 \mathrm{SA} 等算法。

\mathrm{Hash} 非常重要，所以这一块一定要落实喵。

3.1.定义

定义对于一个长度为 n 的字符串 s，其 \mathrm{Hash} 函数为：

其中 base 为定义的倍数，M 为定义的模数。

不难发现这样的话 \mathrm{Hash} 函数的值域为 1\sim M-1，而字符串的种类数是很可能会比这个值域还大的。

也就是，对于两个不一样的字符串，我们也会得到相同的 \mathrm{Hash} 函数值。

这种情况，称之为 \mathrm{Hash} 冲突。

一般来讲，\mathrm{Hash} 冲突会导致 WA。

而在一道题目的数据下是否会 \mathrm{Hash} 冲突，就取决于选择的模数以及倍数了。

在可选择时，倍数会取 131,1331,13331,233 等。

而模数会取 10^9+7,10^9+9,998244353。

个人而言有两个比较推荐的模数 1004535809,167772161，来自于 mrsrz 的一篇题解中，强度高于前面给的三个。

但是切记，选择的 base,M 一定要满足 (base,M)=1。

因为如果 (base,M)\not=1 时，极容易发生 \mathrm{Hash} 冲突。

3.2.实现

根据上面 \mathrm{Hash} 函数的定义，可以很简单的用代码实现：

inline int hsh(char s[],int n)
{
    int h=0;
    for(int j=1;j<=n;j++) h=(h*op+s[j])%mod;
    return h;
}

这个函数代码就已经可以通过 P3370 【模板】字符串哈希了。

但是在实际使用的时候，我们几乎不会这样算 \mathrm{Hash}。

考虑下这样的 \mathrm{Hash} 有什么缺点：

如果每次用到的都只是原本字符串里的一个子串的 \mathrm{Hash}，就得在线 \mathrm{O}(n) 算了，效率非常低下。

但是 \mathrm{Hash} 有非常美妙的性质：可加性。

既然有可加性，那能联想到什么？

前缀和！

那这样的话，\mathrm{Hash} 的实现就成了：

inline void hsh(char s[],int n,int&h[])
{
    for(int j=1;j<=n;j++) h[j]=(h[j-1]*op+s[j])%mod;
}

那使用前缀和后，就可以支持任意子串查询了。

正常的前缀和查询是 h_r-h_{l-1}，那么 \mathrm{Hash} 函数的前缀和也是这样的吗？

并不是的，实则为 h_r-h_{l-1}\times base^{r-l+1}。

为什么是这样的呢？

考虑 \mathrm{Hash} 函数就是把一个字符串转化为一个 base 进制的数再把他映射到 0\sim M-1 这个值域里。

那么两个 base 进制的数相减，肯定要高位对齐才能得到低位喵。

显然的是后面从 n+1 开始的字符都是随意定的，所以对称过去之后肯定是能匹配上的。

那么需要考虑的就是以 i 分界向右到 n 这段是否和左边的字符串对称了。

考虑处理出正反 \mathrm{Hash} 值，直接把这两段拿出来比较即可。

附上 std。

3.3.3.P3501 [POI2010] ANT-Antisymmetry \mathrm{Hash}+二分

简要题意：

• 给定一个长度为 n 的 0/1 字符串 s，求其中异或意义下回文的子串数量。

首先观察题面，发现这个对称是在异或意义下的，那么不难得出要求的串的长度一定为偶数。

这个结论也很好证明，如果是奇数的话异或一下这个位置绝对会不同，自然不可能对称。

接着来考虑怎么做，发现直接 \mathrm{Hash} 不是很好处理，那就再次想到二分。

考虑对于每个点 i，二分其向右能拓展几位，接着再用 \mathrm{Hash} check 即可。

附上超远古抽象马蜂 std。

STC02 - Antisymmetry

双倍经验喵。

3.3.4.P3538 [POI2012] OKR-A Horrible Poem \mathrm{Hash} 求最短循环节+质因数分解优化

简要题意：

• 给出一个长度为 n 的字符串 s，q 次询问，查询 s 某个子串的最短循环节。

首先需要了解的是 \mathrm{Hash} 如何求最短循环节。

如果存在长度为 i 的循环节，怎么判断呢？

考虑把字符串复制一份然后扣掉第一份尾部 i 个字符和第二份头部 i 个字符，就得到了：

那如果存在长度为 i 的循环节，这两部分显然是相等的嘛。

原因就和前面那个 \mathrm{KMP} 的证明部分类似，这里不再赘述。

但是因为枚举效率十分低下，而且这玩意也没有单调性，貌似没法解决了？

注意到循环节长度肯定是子串长度的约数。

所以质因数分解再枚举下就行了。

附上 std。

3.3.5.Matrix Matcher 二维 \mathrm{Hash}

简要题意：

• 给定一个 n\times m 的矩阵 s 和一个 x\times y 的矩阵 t，询问 t 在 s 中出现了多少次，多测。

询问出现次数+小数据，难免让我们想到了枚举每个点 i,j 作为矩阵的左上角尝试和矩阵 t 匹配。

那如何快速匹配呢？考虑 \mathrm{Hash}。

但是貌似没有二维 \mathrm{Hash}？

没事，类比一维的定义一个就行。

我们定义二维 \mathrm{Hash} 函数为：

因为是 \mathrm{Hash} 嘛，所以想要快速查询肯定得再套层前缀和。

再套个二维前缀和，那么这个时候，查询函数就成了：

先给 \mathrm{Hash} 值扔一个数组里排个序，然后用 lower_bound,upper_bound 查询即可，这样就能避免桶。

3.3.6.P3763 [TJOI2017] DNA 可以失配 k 次的字符串匹配问题

简要题意：

• 给定长度为 n 的字符串 s 和长度为 m 的字符串 t，问在可以失配不超过 3 次的情况下 t 在 s 中出现了多少次。
• 多测，t\le10,n,m\le10^5 字符集仅有 A,T,C,G。

这种可失配匹配问题就是 \mathrm{Hash} 的专利了，\mathrm{KMP} 可做不了了。

首先考虑还是得先搞出来 \mathrm{Hash} 值。

接着考虑怎么处理这个最麻烦的失配。

发现失配次数给的不是很多，考虑枚举下失配，每次对这个区间二分得到第一个失配的点即可。

如果最后还没跑到 4 次就没失配了那肯定行的，如果第 4 次失配跑到区间外了也是行的。

判断一下直接扫一遍 s，对于每个位置 i，尝试 s_{i\sim i+m-1} 能否与 t 匹配即可。

附上 std。

3.3.7.P3449 [POI2006] PAL-Palindromes 美妙结论+\mathrm{Hash}

简要题意：

• 给定 n 个回文串，问将其两两拼接能得到多少的回文串（可以和自己拼接）。

首先给出第一个小结论一个回文串的循环节肯定是回文串，这里暂且省略证明。

接着是重点结论，当且仅当两个回文串的最小循环节相同时，他们才能拼成回文串。

首先证充分性：

考虑两个字符串 s,t，相同最小循环节为 s'。

设 s 由 x 个 s' 组成，t 由 y 个 s' 组成。

那么 x+y=\underbrace{s'+s'+\dots+s'}_{x+y}。

显然的是右边这部分是个回文串，充分性得证。

接着来证必要性：

考虑反证法，两个字符串 s,t，s 由 x 个 s' 组成，t 由 y 个 t' 组成，并且 x+y 是回文串。

不难发现，如果这个条件满足，那么 s' 即为 t' 的循环节。

但是 t' 已经是最短循环节了。

所以矛盾，必要性得证。

由此，我们得到了一个超强的结论。

接着用 \mathrm{Hash} 求最短循环节存下来，接着对每种计数就行了。

这点也非常简单，大力枚举就行。

详情可以见 std 喵。

3.3.8.P3546 [POI2012] PRE-Prefixuffix \mathrm{dp}+\mathrm{Hash}

简要题意：

• 定义循环相同为一个字符串移动后缀到首部与另一字符串相同。
• 给定长度为 n 的字符串 s，求 s 在循环相同意义下的最长 border。

考虑暴力：

我们枚举在字符串的首位删去等量字符。

然后求出剩余部分的最长 border。

如果删去的两段相等，那么就对于答案有贡献。

定义 f_i 表示删去 i 个字符后剩余部分的最长 border，则 f_i\le f_{i+1}+2。

这样我们就可以 \mathrm{O}(n) 求出 f 数组，接着用 \mathrm{Hash} 判断下 f_i 这个答案可不可取即可。

附上 std。

3.4.后记

\mathrm{Hash} 太深刻，太强大。

\mathrm{Hash} 的运用不止有字符串 \mathrm{Hash}，还有异或 \mathrm{Hash}，和 \mathrm{Hash} 等众多神兵利器。

剩下的部分，仍是考试热点，如 不可以总司令。

而且 \mathrm{Hash} 可以作为暴力劣正解一只 \log 的情况下拿分。

所以，还是要好好落实喵。

4.\mathrm{Trie}

在不与别的算法组合的情况下，串串中的 \mathrm{Trie} 貌似没有很多用法，所以这章与前面相比将会变的简短很多。

4.1.定义

\mathrm{Trie}，中文名字典树，正如其名，就是一颗像字典的树。

为了方便讲解，这里先扔一张图：

CSA 画的，有点丑见谅。

可以看出来的是 \mathrm{Trie} 中，边的边权变成了一个字符，而从根节点 0 开始往下走路径上的字符就表示了一个字符串。

如 0\rightarrow 6 就组成了字符串 syxqwq。

感觉 \mathrm{Trie} 的结构貌似真的没什么好讲的？

其结构非常好理解，而一般的，我们用 \delta(u,c) 代表 u 节点走过 c 字符到达的节点编号。

4.2.实现

正常使用时，我们还要对每个点记录下他是否是一个字符串的结尾。

比如插入的字符串是 syxqwwq，实际上 \mathrm{Trie} 中有了的字符串有 s，sy，syx，syxq，syxqw，syxqwq。

此时如果来查询 syx，那么也会查询出存在的状态，所以要额外记录下是否是结尾。

下面给出 P8306 【模板】字典树 中插入字符串的代码：

int t;
int n,q,num;
int cnt[3000010],e[3000010][65];
char a[3000010];
int getnum(char c)//获得这个字符的编号
{
    if(c>='A'&&c<='Z') return c-'A';
    else if(c>='a'&&c<='z') return c-'a'+26;
    else return c-'0'+52;
}
void insert()
{
    int p=0,len=strlen(a);
    for(int i=0;i<len;i++)
    {
        int c=getnum(a[i]);
        if(!e[p][c]) e[p][c]=++num;//如果当前边状态不存在，就新建节点
        p=e[p][c];cnt[p]++;//因为字符串可能重，所以用数组记下次数（其实对于这题重不重没区别）
    }
}

接着有关 \mathrm{Trie} 的运用。

最基础也就是板子里的运用：查找一个字符串是否出现。

实现也非常简单，下面直接给出代码：

int query()
{
    int p=0,len=strlen(a);
    for(int i=0;i<len;i++)
    {
        int c=getnum(a[i]);
        if(!e[p][c]) return 0;//如果不存在这个节点那肯定不存在
        p=e[p][c];
    }
    return cnt[p];//如果出现次数为0那也是不存在
}

P2580 于是他错误的点名开始了 纯板子，用于巩固。

4.3.应用

因为是串串相关，所以不会出现 0/1\mathrm{Trie} 喵。

例题也不是很多，就两道。

4.3.1.P4407 [JSOI2009] 电子字典 \mathrm{Trie}+\mathrm{dfs}

简要题意：

• 给定 n 个字符串 s_{1\sim n}，q 次询问，每次询问给定字符串 t，询问 t 操作一次能变成 s_{1\sim n} 中的几个串。
• 操作有三种，分别为：
• 1. 删除串中某个位置的字母；
• 2. 添加一个字母到串中某个位置；
• 3. 替换串中某一位置的一个字母为另一个字母。

查找字符串是否能匹配，这不就 \mathrm{Trie} 板子吗。

接着考虑操作一次，因为只能操作一次，所以想到了 dfs。

直接考虑每一步能否匹配，能匹配的话肯定不会浪费一次操作机会。

而如果失配的话，就尝试操作继续往下 dfs 就好了。

附上超远古 std。

P2536 [AHOI2005] 病毒检测

和上面那题区别不大，不再赘述。

我拿 DFA 写的，就不放代码了。

4.3.2.P6088 [JSOI2015] 字符串树 可持久化 \mathrm{Trie}

看到剖就兴奋了。

简要题意：

• 给定一棵 n 个点的树，树上每条边为一个字符串，q 次询问，求出任意两个节点路径上有多少边代表的字符串以给定字符串为前缀。

树上路径查询，这可太经典了，假设查询的点是 u,v 答案为 ans(u,v)。

那么就有经典拆法：

然后问题就从路径转移到了一个节点到根节点的问题。

想到 \mathrm{Trie}，但是每个节点到根节点的距离都开一个 \mathrm{Trie} 空间直接寄寄。

所以考虑可持久化。

这个可持久化就和线段树的可持久化没有太多区别嘛。

每次新增一个点只多了他到他父亲上的字符串，加进来即可。

每个节点一个版本，不就可持久化 \mathrm{Trie} 做完了嘛。

代码太丑了，不放了。

4.4.后记

光光用 \mathrm{Trie} 的串串题还是不多的，所以这个篇章也就这么长。

但是 \mathrm{Trie} 是非常重要的，一定需要掌握的。

因为，\mathrm{Trie} 会再次出现在 \mathrm{ACAM}，广义 \mathrm{SAM}，\mathrm{PAM} 中。

\mathrm{Trie}：请相信我们很快会再次相见的。

5.\mathrm{Manacher}

\mathrm{Manacher}，在回文方面的利器。

代码简短线性复杂度，在回文的题目正常能吊打 \mathrm{KMP}，\mathrm{Hash}。

因为是个算法而且基本没有额外定义，所以直接从例题开讲。

5.1.算法思想与实现

首先，我们要了解 \mathrm{Manacher} 能解决什么问题。

比如 P3805 【模板】manacher：

其简要题意即为：

• 给定一个字符串 s，求 s 的最长回文子串。

这个字符串 s 的长度就非常吓人，达到了 10^7，也告诉我们一定要用小常 \mathrm{O}(n) 算法。

接着来看题目，题意非常精简：最长回文子串。

考虑这种东西怎么找？

可以从一个点 i 开始，考虑最多能往两边扩展多少格，再全部取个 \max 即为答案。

那么问题就转化成了对于每个 1\le i\le n，如何快速求出以其为中心的回文串长度。

珂以考虑 \mathrm{Hash}+二分，但是这样的复杂度是 \mathrm{O}(n\log n)，理论不能通过此题。但这题数据有点水。

重点来讲讲正片 \mathrm{Manacher} 算法。

首先对于以 i 为对称中心的字符串分个类，就知道分为长度为奇/偶数两种。

不妨先考虑下长为奇数的回文子串如何求：

假设我们已经求出了 1\sim i 的每个点为对称中心的最长扩展长度 h_{1\sim i}。

接着来考虑怎么求 h_{i+1}。

假设我们现在已经求到的回文子串的最远右端点为 r。

这个时候又分为两种情况：

1. 当 i\le r 时： 这个时候我们考虑利用已经求出来的字符串得到答案：

   \dots ,\overbrace{s_l,\dots,\underbrace{s_{j-h_j+1},\dots,s_j,\dots,s_{j+h_j-1}}_{palindrome},\dots,\underbrace{s_{i-h_j+1},\dots,s_i,\dots,s_{i+h_j-1}}_{palindrome},\dots,s_r}^{palindrome},\dots

   显然的是 l\sim r 为最长回文子串且包含 i 的时候， i 的最优情况是把另外半边与他回文的 j 的最右回文子串对称过来。 但是有一种可能性就是你对称过来之后 i+h_j-1>r，这个情况显然是不一定成立的，所以更新的值要和 r-i 取 \min。

2. 当 i>r 时： 这个时候考虑直接用暴力头尾扩展回文子串。 记得拓展完后更新最右回文子串。

根据这个思想就可以很简单实现代码：

inline void manacher(char s[],int h[],int n)
{
    for(int i=1,r=0,md=1;i<n;i++)
    {
        h[i]=i<=r?min(h[md*2-i],r-i):1;
        while(s[i+h[i]]==s[i-h[i]]) h[i]++;
        if(h[i]+i>r) r=h[i]+i,md=i;
    }
}

这个时候就有个很棘手的事情，就是怎么处理偶数长度的回文串呢？

考虑在字符串中的每两个字符间插入 #，再在头部放一个 -（因为本文全是从 1 开始的，所以 0 不附特殊值可能寄）。

那这样的话所有偶数的情况都被转化为了奇数的情况，可以用上面那个代码处理。

而这步处理，只需要在读入的时候完成即可：

inline void red(char s[],int&n)
{
    s[0]='-',s[++n]='#';s[++n]=getchar();
    while(chk(s[n])) s[n]=getchar();
    while(ck(s[n])) s[++n]='#',s[++n]=getchar();n--;
}

P1723 高手过愚人节

双倍经验喵。

5.2.应用

\mathrm{Manacher} 算法的运用，貌似都是比较纯的套板子？

或许是因为我浅尝辄止导致的吧，但是这里给出的几道例题都不是很难喵。

5.2.1.P9606 [CERC2019] ABB \mathrm{Manacher} 做法

又是这个题！

这次我们来讲 \mathrm{Manacher} 算法。

类似于前面 \mathrm{KMP} 做法的思路转化，转化完后题意就成了：求最长后缀回文。

接着考虑怎么用 \mathrm{Manacher} 求最长后缀回文。

其实非常简单，就在板子上改一点，判断一下当前回文是不是延长到串尾了。

第一个延长到串尾的肯定是最长的，所以直接打断跳出去就行了。

附上 std。

练习题还是那两经验。

5.2.2.P4287 [SHOI2011] 双倍回文 \mathrm{Manacher} 好题

这题貌似乱搞做法一堆，还有一种正解是 \mathrm{Hash+PAM}。

但这里我们重点讲 \mathrm{Manacher}。

简要题意：

• 给定长度为 n 的字符串 s，求其最长双倍回文子串。
• 定义双倍回文为由两个一模一样的回文串组成的串。

首先我们可以很简单的得出普通的最长回文子串，直接上 \mathrm{Manacher} 就行了。

接着考虑怎么变成双倍回文。

这个时候贯穿 \mathrm{Manacher} 的朴素思想，直接考虑在更新 r 端点的时候尝试更新答案即可。

怎么尝试呢？

扫一下这个字符串看看他的左半边是不是回文串即可。

因为他本身是个回文串，所以他的左半边若是回文串，对称下右半边也就是回文串。

这样也就达成了双倍回文的条件。

具体实现可以参考第一篇题解。

复杂度是正确的，因为你把所有往右扫回文子串这个操作全部剥下来考虑。

不难发现其是单调的，所以直接朴素操作是线性的。

这样就完成了这题。

附上 std。

5.2.3.P6216 回文匹配 \mathrm{Manacher}+\mathrm{KMP}

简要题意：

• 给定长度为 n 的字符串 s 和长度为 m 的字符串 t，定义分数为一个字符串中 t 的出现次数。
• 问 s 所有回文子串的分数和。

看到回文子串，很快啊，直接先上个 \mathrm{Manacher} 再说。

然后考虑下怎么算这个逆天的分数。

因为是出现次数，所以先考虑对着 s,t 跑一遍 \mathrm{KMP} 得到所有的出现位置。

给这些位置标 1，然后加次前缀和，我们就可以很快的算出每个回文子串的分数，总复杂度是 \mathrm{O}(n^2)。

接着考虑如何优化。

考虑目前的前缀和数组是 s。

我们目前对于一个长回文串，做法是枚举他的每一个子串然后前缀和加上分数。

考虑从这个式子下手：

其中 mid=\lceil{\frac{m}{2}}\rceil。

这个式子就可以二阶前缀和了，计算方法就是 ss_l+ss_r-2\times ss_{(r-l)/2}。

然后就完美完成了！

记得取模！

附上 std。

5.3.后记

在未学习 \mathrm{PAM} 这种逆天方法前，\mathrm{Manacher} 是最好用的有关回文的算法。（貌似还挺简单的？）

但是题目貌似真的不是很多，就当个方法掌握好了。

6.\mathrm{Z} 函数

那么这两个被括号括起来的部分就是相等的。

然后我们考虑这东西和 i 有什么关系。

显然的是我们知道 l<i，因为 l 是取的前面已有的一个匹配段，必然是在 [1,i-1] 内的。

接着我们进行分类讨论，如果 i\le r，那么还是画图考虑。

由于上括号划的这一段是相同的，所以下括号划的这一段显然也是相同的。

也就是在这种情况我们可以直接给 Z_i 赋值为 Z_{i-l+1}。

接着考虑超过去的情况。

直接暴力做即可！

具体的，我们对目前的这个算法进行复杂度分析。

如果看过 \mathrm{Manacher} 的分析，那么就会发现这东西完全没区别。

考虑对 r 进行分析，会发现 r 是单增的，每次成功的比较都会让 r+1，而不成功的都会让循环的 i+1。

所以总的复杂度就是 O(n)，不过又是一个均摊算法。

对于代码实现，个人认为写的和 \mathrm{Manacher} 一样会比较好看好记好写不易挂。

inline void get_Z(char s[],int n,int z[])
{
    for(int i=2,l=1,r=0;i<=n;i++)
    {
        z[i]=i>r?0:min(z[i-l+1],r-i+1);
        while(i+z[i]<=n&&s[z[i]+1]==s[i+z[i]]) z[i]++;
        if(i+z[i]-1>r) l=i,r=i+z[i]-1;
    }z[1]=n;
}

6.2.应用

这个运用的话也没多少题，我努力找了下，唯一好一点的题还是 XYD 的题（）。

所以可能没法提交只能看看题面想想题了（）。

如果有我没收录的题欢迎私信供题喵。

6.2.1.P5410 【模板】扩展 KMP/exKMP（Z 函数）

简要题意：

• 给定字符串 s,t，求 t 的 \mathrm{Z} 函数，并求 s 以 t 为前缀的 \mathrm{Z} 函数。

首先第一问我们已经会了，现在的问题就是第二问。

对此我们有两种解决方法。

其实和 \mathrm{KMP} 求字符串匹配就是一样的嘛。

1. 把 t 和 s 拼起来，中间插入特殊字符 \mathrm{Z} 函数，那么就可以直接得到两问的答案。
2. 利用 t 的 \mathrm{Z} 函数重新跑一边求对于 s 而言的 ext。

划着括号的两部分显然是相同的，对齐的部分也显然是相同的。

那么我们就知道前缀 i-1 是前缀 i+z_i-1 的周期，也就是答案的取值即为 \lfloor\frac{z_i}{i}\rfloor+1。

然后我们考虑奇数次的限制。

前面的 i 个字符已经确定了，那么最后面的 C 也是可以确定的。

P3808 AC 自动机（简单版）

附上 std。

P3796 AC 自动机（简单版 II）

附上究极无敌远古抽象马蜂 std。

还有个双倍经验喵：Dominating Patterns

P5357 【模板】AC 自动机

这个题要略微优化一二。

附上 std。

P3121 [USACO15FEB] Censoring G

纯板子。

7.3.应用

简要题意：

• 给定 n 个只包含大写字母的字符串，随机生成一个长度为 m 的只包含大写字母的字符串，若其中含有前面给出的字符串，则是可以读懂的。
• 问可以读懂的字符串一共有多少个，答案对 10007 取模。

首先发现题目条件里是含有就可以算读懂，如果直接考虑做的话还要去重非常麻烦。

所以正难则反，考虑容斥，用总个数减去读不懂的个数。

总个数显然就是 26^m。

考虑如何求读不懂的个数。

首先对所有串建出 \mathrm{ACAM}，接着考虑设计个 \mathrm{dp} 转移：

P3041 [USACO12JAN] Video Game G

比较简单的 \mathrm{ACAM} 上 \mathrm{dp}。

P3311 [SDOI2014] 数数

比较烦的 \mathrm{ACAM} 上 \mathrm{dp}，注意细节。

附上 std。

You Are Given Some Strings...

一个小思路转化+\mathrm{dp}。

附上 std。

P2292 [HNOI2004] L 语言

正解应该是状压 \mathrm{dp}，但是懒癌的我写的是乱搞优化 \mathrm{dp}。

附上 std。

P4045 [JSOI2009] 密码 和 Password Suspects

双倍经验，都在题解区里了。

Digits of Number Pi

简要题意：

• 给定一个长度为 n 的包含小写字母和 B,P，的字符串 s。
• 最开始字符串 t 为空。
• 有 q 次询问，每次询问给出 x,y 表示询问第 x 次打印的 t 在第 y 次打印的 t 里出现几次。

多模匹配计数问题，首先考虑 \mathrm{ACAM}。

那 \mathrm{ACAM} 怎么做呢？

这个题的串串里还有奇怪的操作，插入貌似不能用以前那种。

没事，题面怎么写，我们插入函数就怎么写：

inline void insert(char s[],int n)
{
    int u=0;
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='P') Q[++cnt]=u;
        else
            if(s[i]=='B') u=t[u].f;
            else
            {
                int v=s[i]-'a';
                if(!t[u].v[v]) t[u].v[v]=++tot,t[tot].f=u;
                u=t[u].v[v];
            }
        t[u].ed=1;
    }
}

对于每一次输出的字符串，再给他的状态对应的点存储下来。

每次往下加字符就记录下 fa 方便回退操作。

然后再和正常的一样给末尾点打上结尾标记。

现在，我们有了一只 \mathrm{ACAM}。

接着来考虑怎么查询。

查询操作，相当于查询 q_y 这个点的状态的所有的子串在 x 次打印中的串中的出现次数之和。

考虑把在第 x 打印的串的子串节点权值全部加上。

那么变成了查询 q_y 这个点对应状态的子串节点权值和。

发现存在一次打印的串被查询多次而有几次打印的串却没被查询过的情况。

考虑把询问离线下来，对于每一个 y 进行回答。

接着发现子串是难以突破的关键。

想到什么？

e-Government

和上面这题基本没区别，纯板子，用于巩固提升。

std。

Indie Album

这题思维有一定难度。

考虑不对 s 建 \mathrm{ACAM}，不然就要动态更改结构。

所以我们考虑对 t 建 \mathrm{ACAM}，剩下部分就和上面没区别了。

std。

[CERC2018] The ABCD Murderer

简单 \mathrm{DS+dp}，代码和思路可以见题解。

7.3.5.Death DBMS \mathrm{ACAM}+树剖！

简要题意：

• 给出 n,m，然后给出 n 个字符串，每个字符串都有一个权值，最初权值都为 0。
• 然后有 m 个操作，操作有两种类型：
  1. 将第 i 个字符串的权值修改为 x。
  2. 给出一个字符串 t，求所有是 t 的子串的字符串的权值的最大值。

乍一看好像和前面那题没有区别，因为也是一个查询子串的权值问题。

所以应该也要建出 \mathrm{Fail} 树在上面跑 \mathrm{BIT}？

询问的是最大值！

GRE - GRE Words

简要题意：

• 给定 2\times n 个序列，其中第 i 个和第 i+1 个的编号都是 \frac{i}{2}(i\bmod2\equiv0) 。
• 再给定 q 个序列，询问这个序列是前面多少个不同编号的序列的子串。
• 最后在输出每个编号的序列包含了多少个不同的询问序列。
• 也就是对于一个编号，他的两个序列得到的答案是或的关系。

这个题，只能说，泰裤辣！

Warning：请确保自己已经深刻了解 \mathrm{Fail} 树的意义。

首先这种序列但又是子串的问题，考虑 \mathrm{ACAM}。

但是 \mathrm{ACAM} 实质是一只字典图，这么大的值域不得炸光了？

所以考虑使用 map 来代替原本建树里的 v 数组。

接着发现每个编号他有两个序列，到时候统计还要去重，不得烦死。

所以考虑直接把这两个序列拼接起来，可以在中间插入一个 -1 来间隔开。

接着再考虑把询问序列也给扔 \mathrm{ACAM} 里方便后续操作。

接着这个问题又变成了统计出现过的子串个数，想到和上面类似的方法：

\mathrm{Fail} 树+\mathrm{BIT}！

但这样是有点问题的，我们先按照这个思路给题目转化过来看看：

1. 对于第一问，就是对每个编号的序列的点覆盖到 0 节点然后取个并集的修改。 查询即为单点查询。

2. 而对于第二问，就是询问序列状态单点修改。 查询即为对每个编号从 0 到结尾链查询。

这玩意好做吗？

显然不好做，覆盖是什么神仙玩意啊。

所以来考虑怎么转化题意。

首先对于第一问，可以转化为树上单点修改，子树查询。

但是显然的是这样也会有重复部分，所以要去重。

那怎么去重呢？

我们发现，开始重复的位置就是两个修改了的点的 \mathrm{LCA} 的位置，所以只需要给他们的 \mathrm{LCA} 这里点权 -1 就行了。

但这样就做完了吗？

因为修改的点有很多，所以很多地方都会重，但是我们去重肯定要去掉一个最近的 \mathrm{LCA}。

也就是，题意转化了求在树上的 k 个点的最小连通子图会经过的 \mathrm{LCA}。

这玩意有一道题目：P3320 [SDOI2015] 寻宝游戏和经验Archaeology。

首先我们能知道的一个很显然的结论，就是这样求出来的 \mathrm{LCA} 个数不会超过 k-1 个。

因为一个点向上走到一个 \mathrm{LCA} 至少能再向下走到另外一个点。

这里先给出结论：把这些点按照 \mathrm{dfn} 序排序后，相邻的两个点取 \mathrm{LCA} 即为最近 \mathrm{LCA}。

接着考虑证明：

首先考虑排序的步骤。

我们把每个点的所有儿子按照 \mathrm{dfn} 序排序，使得在主观意义上小的 \mathrm{dfn} 序的点在大的左边。

比如这张图（点的编号表示 \mathrm{dfn} 序）：

假设我取出的带标号的点为 a_i，并且只考虑这个点与 a_{i\sim n} 的贡献（a_i 与前面贡献已经在 a_{1\sim i-1} 的时候算完了）。

考虑下这个 \mathrm{LCA} 要满足的条件是能走到 a_{i+1\sim n} 中的任意一个点。

显然的是这个 \mathrm{LCA} 肯定在 1\rightarrow a_i 的路径上，且由定义得要与 a_i 最近，也就是 a_i 往上跳最少的步数。

考虑每个点他对应子树的 \mathrm{dfn} 序是一个区间，设点 i 对应的区间右端点为 ed_i，那么显然的是 i 的 \mathrm{dfn} 序区间是 dfn_i\sim ed_i。

因为我们只要求 a_{i+1\sim n} 的贡献，而他们的 \mathrm{dfn} 序又是单增的，所以只需要考虑 ed_i 即可。

显然当 a_i 这个点不断往上跳时，其 ed 为单调不减（因为父亲节点他的 ed 是 \max\{ed_{son}\} ）。

而 a_i 跳到的点 u 能到达 v 的充分条件是 dfn_v\le ed_u（由前面的排序得 dfn_{a_i}<dfn_v）。

所以 dep_{\mathrm{LCA}(a_i,a_{i+2})}\le dep_{\mathrm{LCA}(a_i,a_{i+1})}。

也就是 \mathrm{LCA}(a_i,a_{i+1}) 即为最近的 \mathrm{LCA}。

所以这个结论就成立了。

那么回到正题，这里我们只需要对于每个编号的序列的所有状态的点一路修改上去，然后去重就行了。

查询即为前面所说的子树查询。

//tt为 BIT，id[i]为编号 i 对应的状态的结尾点，q[i]为第 i 次询问对应的状态结尾点
memset(tt.c,0,sizeof tt.c);
for(int i=1;i<=n;i++)
{
    //修改
    int u=id[i],tot=0;
    while(u) a[++tot]=u,tt.modify(dfn[u],1),u=ac.t[u].fa;
    //去重
    sort(a+1,a+1+tot,cmp);
    for(int j=1;j<tot;j++) tt.modify(dfn[LCA(a[j],a[j+1])],-1);
}//查询
for(int i=1,u;i<=m;i++) u=q[i],print(tt.query(dfn[u],dfn[u]+si[u]-1)),puts("");

而对于第二问，类似的，只不过是修改查询对调：

memset(tt.c,0,sizeof tt.c);
for(int i=1,u;i<=m;i++) u=q[i],tt.mdf(dfn[u],dfn[u]+si[u]-1,1);
for(int i=1;i<=n;i++)
{
    int u=id[i],tot=0,res=0;
    while(u) a[++tot]=u,res+=tt.query(dfn[u]),u=ac.t[u].fa;
    sort(a+1,a+1+tot,cmp);for(int j=1;j<tot;j++) res-=tt.query(dfn[LCA(a[j],a[j+1])]);
    print(res);putchar(' ');
}

最后，附上 std。

这一块的练习题主要特点是难于上面那块。

Mike and Friends

这题好像没那么难？感觉 2800 有点高了。

如果写过 \mathrm{P4211} 的话应该不难想。

std。

P5840 [COCI2015] Divljak

std。

JZPGYZ - Sevenk Love Oimaster

std。

这两题，是类双倍经验，有一定难度，可以思考一二。

7.3.7.GEN - Text Generator \mathrm{ACAM}+矩阵优化~\mathrm{dp}

简要题意：

• 给定 n 个字符串，求包含这 n 个字符串中的任意一个的长度为 l 的字符串有多少种。

第一眼看到这题，不就是 6.3.2.P4052 [JSOI2007] 文本生成器 吗？

仔细一看，不太对劲的样子，这个 l\le10^6 早把文本生成器的做法干爆了。

（如果忘记文本生成器怎么做了，可以去前面看看喵。）

下面重点来讲下这个玩意怎么优化。

因为我们的 \mathrm{dp} 的转移是一步步推过来的，那么 dp_l 就是从 dp_0 转移 l 步得到的。

也就是相当于走了 l 步。

也就是在 \mathrm{ACAM} 上走了 l 步。

因为 \mathrm{ACAM} 上的点不是很多，所以点直接两两走的方案数可以用邻接矩阵存起来。

那么，走 1 步的矩阵是不是就为初始矩阵？

如果我们把走 1 步的矩阵相乘，是不是得到了走 2 步的矩阵？

再次把走 2 步的矩阵相乘，是不是得到了走 4 步的矩阵？

那是不是就可以矩阵快速幂优化走 l 步这个过程？

因为从初始状态开始，最后走到哪个状态结尾都有可能，所以要取矩阵的第一行答案相加。

还有这题略卡常，无用的状态要直接扔掉。

std。

Legen...

这个题更有难度一点，需要一定的思维转化。

详情可以见 CF696D 解题报告。

7.3.8.String Set Queries 可持久化 \mathrm{ACAM}

非常好玩的题。

简要题意：

查询所有字符串在给定字符串中的出现次数这个操作，考虑用 \mathrm{ACAM} 来解决。

接着考虑处理其他两种操作，因为删不太好弄，所以考虑把他变成减去其出现次数。

实现上也就是将删的字符串插入另一个 \mathrm{ACAM} 中，然后查询时答案减去这个 \mathrm{ACAM} 中查询出的答案。

接着考虑本题的难点：强制在线。

这点就让 \mathrm{ACAM} 非常难办了，总不可能每加一个字符串就重构一遍 \mathrm{Fail} 指针吧。

那么我们就要让重构 \mathrm{Fail} 指针的次数最小，能不重构就不重构。

这样会想到什么呢？

二进制分组！

具体的，类似于 2048，把字符串按照二进制分组后，对于每一块建一个 \mathrm{ACAM}，碰到相同大小的块就合并暴力重构。

再具体些，比如大小为 4 的块中，就有 4 个字符串，并对他建了个 \mathrm{ACAM}。

如果再来了个大小为 4 的块，就将他们合并为大小为 8 的块，暴力重构 \mathrm{Fail} 指针。

因为最后合并出来的最大块也仅为 n，所以合并步骤不会超过 \log n 次，复杂度仅多一只 \log 完成在线。

最后查询的时候遍历每个块的 \mathrm{ACAM} 算答案就行了。

附上 std。

ADAJOBS

这个题可以离线做但是也可以用在线做法写。

std。

7.3.9.Duff is Mad/P7582 「RdOI R2」风雨(rain) 根号相关的 \mathrm{ACAM}

按顺序来看两个题好了，先是 Duff is Mad。

简要题意：

• 给定 n 个字符串 s_{1 \dots n}。

别把题面看错了，注意是区间串在单串中的出现次数。

这个就不太好做了，如果是单串在区间中的出现次数话就非常好处理。

考虑怎么暴力用 \mathrm{ACAM} 处理。

先建 \mathrm{Fail} 树，对于区间 [l,r] 的串全部都子树加。

查询直接暴力跳单串的每一个点，把权值加上就行了。

这样的话我们的复杂度是 O(n^2\log n) 的，因为字符串长度和 n 同阶。

不难发现，因为是加和，所以区间 [l,r] 可以被拆为 [1,r]-[1,l-1]。

但因为我们的单串是暴力跳的，所以复杂度还是高居不下。

那这个时候还能怎么处理呢？

考虑把子树加链查改掉，改成链加子树查。

前者是对于区间的每个串子树加，然后单点查询问串的每个位置。

后者是对于询问串整个链加，然后对于区间的每个串查询权值即可。

看起来这两种方法是没有区别的，但是仔细分析我们就会发现，这两种方法的复杂度分别是：

P9935 [NFLSPC #6] 啊，忘记了。 折磨题，还在补。

7.4.后记

注意，请区分这里的 \mathrm{SA} 和模拟退火那个 \mathrm{SA}。

此处的 \mathrm{SA} 指的是 \mathrm{Suffix~Array}，即为后缀数组，用于处理字符串的一系列问题。

用途较为广泛，可以处理 \mathrm{ACAM} 不能处理的本质不同子串等问题。

8.1.定义

首先后缀的概念就非常清楚了，取长度为 n 的字符串 s 的 s_{i\sim n} 即为 s 的后缀。

而 sa_i 便是将 s 的所有后缀按照字典序排序后，排名为 i 的后缀以 sa_i 为头。

要是 \mathrm{SA} 只能进行快速的后缀排序的话，那他的应用会被大大限制。

所以其与 \mathrm{LCP} 也有联系。

定义 height_i 表示 \mathrm{LCP}(sa_i,sa_{i-1})。

特殊的，对于 height_1，其值可视为 0。

既然定义了 height，接着就来考虑怎么快速求 height。

这里需要用到一个引理：height 引理。

其内容即为：height_{rk_i}\ge height_{rk_{i-1}}-1。

• 当 height_{rk_{i-1}}\le1 时：
  • 根据定义 height_{rk_i}\ge0，上述式子显然成立。
• 当 height_{rk_{i-1}}>1 时：
  • 不妨设 \mathrm{LCP}(sa_{rk_{i-1}},sa_{rk_{i-1}-1}) 为 s+Y，其中 s 为一个字符，Y 表示一个字符串，加号表示连接。
  • 那么设 sa_{rk_{i-1}} 这个后缀为 s+Y+X；sa_{rk_{i-1}-1} 这个后缀为 s+Y+F，其中 X,F 表示两个不同的字符串。
  • 那么，后缀 sa_{rk_i} 就可以表示为 Y+X，并且，存在后缀 Y+F（就是上面那两个字符串各剥掉第一位）。
  • 显然的是后缀 sa_{rk_i-1} 被约束在了 Y+F 和 Y+X 中。
  • 既然这个后缀在这中间，那么他也必然可以表示为 Y+? 的形式，其中 F\le?<X。
  • 那么 \mathrm{LCP}(sa_{rk_i},sa_{rk_i-1}) 就至少为 |Y| 了，也就是 height_{rk_{i-1}}-1。
• 证毕！

具体的求 height 数组，根据这个引理暴力即可：

inline void get_height(int n,int h[],int rk[],char s[])
{
    int k=0;
    for(int i=1;i<=n;i++) rk[sa[i]]=i;
    for(int i=1,j;i<=n;i++)
    {
        if(rk[i]==1) continue;if(k) k--;j=sa[rk[i]-1];
        while(j+k<=n&&i+k<=n&&s[i+k]==s[j+k]) k++;
        h[rk[i]]=k;
    }
}

复杂度为严格 O(n)，因为其中的 k 最多减 n 次，而加最多加到 n。

接着有一些有关于 height 数组的推论：

1. \mathrm{LCP}(sa_i,sa_j)=\min(height_{i+1\sim j}),i<j

   这个结论挺显然的。

   因为后缀是被排序过的，所以他的每位字符变大是从后往前单调不减的。

   也就是，如果存在 i<k\le j 满足 height_k<height_{k-1}，那么后缀 k 必然是在 height_k+1 这一位变大了一点。

   那么显然的是后缀 sa_i 的前 height_k+1 位必然小于后缀 k 的 height_k+1 位小于等于后缀 sa_j 的 height_k+1 位。

   因为后缀都是经过排序的，所以这个变换过程必然是单调的，也就是 \mathrm{LCP}(sa_i,sa_j)\le \min(height_{i+1\sim j}),i<j。

   接着来证为什么能取等。

   因为 height_{i+1\sim j}\ge \min(height_{i+1\sim j})，所以他前面至少有 \min(height_{i+1\sim j}) 位是相等的。

   也就是能够取等，得证。

2. 比较 s_{x\sim y} 和 s_{i\sim j} 大小：

   分两种情况：

   • - $s_{x\sim y}<s_{i\sim j}$ 即为 $y-x+1<j-i+1$。
   • 否则：

   这个有点显然了，就不写严谨的证明了。

3. 本质不同子串个数：

   因为后缀满足开头的位置两两不相同，所以答案即为每个后缀的前缀去重。

   考虑怎么样的情况才会重复，即为相同的前缀。

   这不就 \mathrm{LCP} 的前缀吗，那么重复前缀的数量即为 \sum\limits^n_{i=1}height_i，拿全部子串数 \frac{n(n-1)}{2} 减下即可。

   SUBST1 - New Distinct Substrings 例题喵。

   std。

   双倍经验。

   略微扩展的板子。

   比较有意思的相关题，题解。

其他相关就在后面题目中再说了。

8.4.应用

LCS，LCS2，P5546 [POI2000] 公共串，LONGCS，DNA Sequencing。

都是 \mathrm{LCS} 问题喵，考虑求出 height 后，用双指针找区间外加单调队列求答案即可。

当然也可以二分，但是复杂度多一个 \log n。

std for P5546 喵。

8.4.2.P4070 [SDOI2016] 生成魔咒 \mathrm{SA}+字符串翻转

这个题，用到的东西，能叫他 \mathrm{PA}，也就是 Prefix~Arrary 吗，不懂欸。

简要题意：

首先看到本质不同子串，首先考虑 \mathrm{SA}。

但是这个操作是在末尾加上字符，后缀在不断变化，显然的是不太好做。

那怎么办呢？

考虑把字符串翻转然后倒着扫。

也就相当于把 \mathrm{SA} 变为了 \mathrm{PA}。

那么每次多的就是一个新的前缀，也就是翻转串的一个新的后缀。

考虑本质不同的子串个数求法，是子串个数减去重复个数。

那么新的后缀就相当于，插入在了一个原本排序好的 height 序列中。

按照 rk 排序，重复的部分当且仅当新的后缀的前后与其求的 \mathrm{LCP} 嘛。

考虑扔进 set 里去，然后对于每个新的后缀找到其位置判断前后缀取 \max(\mathrm{LCP}) 即可。

具体可以看代码了。

std 喵。

8.4.3.P3975 [TJOI2015] 弦论 \mathrm{SA} 求第 k 小子串

比较经典了，但是我好像写的有点复杂。

简要题意：

• 给定长度为 n 的字符串 s 和两个数字 op,k。
• 若 op=0，则询问 s 的本质不同第 k 小子串。
• 否则询问 s 的第 k 小子串（可以本质相同）。
• 若不存在第 k 小，输出 -1。
• n\le5\times10^5,k\le10^9

直接做这个问题还是稍微有点难度的，先来看一道他的子问题：SUBLEX。

这个问题中只有 op=0 的情况。

考虑 \mathrm{SA} 具有的优秀性质：

后缀有序。

这意味着后缀的前缀也是有序的。

那么我们就可以求出不重复子串个数的前缀和 ss 数组。

对于给定的 k，二分出第一个位置 i 满足 ss_i\ge k，接着直接算出右端点输出即可。

复杂度 O(T\times k)，瓶颈在输出，所以其实可以不用二分的。

std 喵。

接着来考虑原问题中 op=1 的情况。

貌似不是很好处理？

因为要求的是字典序第 k 小，所以还是得先借用 \mathrm{SA} 后缀有序的优秀性质。

先按排序后的顺序枚举每个后缀，再枚举字母，二分出这个字母的右端点。

考虑类似于 op=0 时的前缀和，就可以快速查询出生成字符串个数。

找到之后再算出右端点输出即可。

因为枚举的后缀和字母大小都是单增的，所以肯定是第 k 小。

std。

具体实现有些细节喵。

8.4.4.P3181 [HAOI2016] 找相同字符 \mathrm{SA}+单调栈

简要题意：

• 给定长度为 n 的字符串 s 和长度为 m 的字符串 t。
• 问截取出两段相同子串有多少种方案。

考虑先转化题意，其本质即为算 s 的所有后缀与 t 的所有后缀的 \mathrm{LCP} 长度之和。

因为每个后缀的开头位置都不同，所以其公共前缀均为答案。

而对于两个字符串，其公共前缀数量即为 \mathrm{LCP} 长度。

这样便完成了第一步的转化。

接着发现 s 的所有后缀和 t 的所有后缀这个条件导致题目十分难处理。

不妨先来考虑这题的弱化版：P4248 [AHOI2013] 差异。

这个弱化版即为求所有后缀的 \mathrm{LCP} 长度之和。

考虑两个后缀 i,j 的 \mathrm{LCP} 长度即为 \min(height_{i+1\sim j})。

但是如果考虑枚举后缀的话复杂度就会难免来到 n^2 以上。

不难发现，height_i 对于这个区间 [l,r] 的答案有贡献当且仅当 height_i=\min(height_{l+1,r}),l+1\le i\le r。

考虑当一个区间单调的向左/右扩展时最小值单调，可以考虑单调栈维护求出每个 height_i 有贡献的最大区间 [l,r]。

那么具体的这个 height_i 的贡献即为 height_i\times(r-i)\times (i-l)，也就是包含 i 的子区间都有贡献。

因为题目原因所以最后求出来的值还要乘 2，最后用总子串长度减去这个值即为答案。

std 喵。

接着来考虑原题目。

可以考虑容斥，那么答案即为 s+\#+t 的所有后缀的 \mathrm{LCP} 长度之和减去 s,t 的所有后缀的 \mathrm{LCP} 长度之和。

而求所有后缀的 \mathrm{LCP} 长度之和就是前文所述单调栈了。

std 喵。

8.4.5.P3649 [APIO2014] 回文串 \mathrm{SA}+\mathrm{Manacher}+\mathrm{ST} 表

一道感觉像是综合但又感觉像是单纯拼接算法的题目。

简要题意：

• 定义 s 的一个子串存在值为出现次数\times子串长度。
• 求所有回文子串中的最大存在值。

考虑一部分一部分地拆分解决。

首先考虑如何处理存在值，考虑使用 \mathrm{SA}+\mathrm{ST} 表的方式 O(\log n) 得到子串出现次数。

这样存在值就直接按照题意中给的公式计算即可。

接着考虑如何处理回文子串这个问题。

首先我们要知道一点，就是回文子串的总个数是线性的。

具体有关这一点的证明可以见回文树中的状态总数为线性的证明。

由这一点，我们考虑使用 \mathrm{Manacher} 求出 s 的回文子串。

在每求出一个新的回文子串时，使用 \mathrm{SA} 进行查询这个回文子串的存在值。

最后取 \max 即可。

std 喵。