字符串小结（持续更新）
ez_lcw
2020-11-06 08:11:30
~~只是给忘记模板时的我看的~~
# AC自动机
## 大概流程
首先对所有模式串建出 $Trie$ 树，并标记。
**$fail$ 的定义：设 $i$ 节点所代表的字符串为 $S$，则 $fail_i$ 表示 $S$ 的所有后缀里面，在 $Trie$ 树中出现过的最长的那个串所代表的节点。**
然后通过 $\texttt{bfs}$ 求出 $fail$，代码如下：
```cpp
void getfail()
{
queue<int>q;
for(int i=0;i<26;i++)
if(t[0].ch[i])
q.push(t[0].ch[i]);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=0;i<26;i++)
{
if(t[u].ch[i])
{
t[t[u].ch[i]].fail=t[t[u].fail].ch[i];
q.push(t[u].ch[i]);
}
else t[u].ch[i]=t[t[u].fail].ch[i];//tag1
}
}
}
```
其中为什么 $tag_1$ 处可以将 $u$ 的儿子直接指向 $fail_u$ 的儿子 $v$：
首先实际的操作应该是新建一个虚拟节点 $new$，使 $new$ 为 $u$ 的儿子，且 $fail_{new}=v$。
又由于 $new$ 本身是新建的节点，没有任何儿子，所以 $new$ 的儿子全都是要靠新建虚拟节点构成。
所以 $new$ 的子树其实和 $v$ 的子树是一模一样的。
那我们不妨用同一棵子树表示他们，也就是说让 $u$ 的儿子指向 $v$ 而不是新建节点。
然后由于 $new$ 树的 $fail$ 全部都是指向 $v$ 树的，所以合并到一起不会对 $fail$ 产生影响。
那么 $\operatorname{getfail}()$ 之后原来的 $Trie$ 树就会变成一个 DAG 了。
## 实际应用
### 一、模式串与文本串匹配上的应用
#### 原理
首先通过递归 $fail$，就可以遍历某个串的所有在模式串中出现过的后缀。
同样，如果**建立 $fail$ 树（$fail_i\to i$）**，就可以通过遍历某一个点 $u$ 的子树（设 $u$ 所代表的串为 $s$），遍历所有以 $s$ 为后缀的串。（也就是往 $s$ 的前面加字符）
其次，对于原 $Trie$ 树中的某一个节点 $u$（设其代表的串为 $s$），可以遍历统计 $u$ 子树内的所有点，遍历所有以 $s$ 为前缀的串。（也就是往 $u$ 后面加字符）
那么综合上面两个操作，对于某个串 $t$，我们可以求出所有满足 $t$ 是 $s$ 的子串的 $s$ 串的信息。
时间复杂度为 $O(n)$（遍历一遍 $Trie$ 树+一遍 $fail$ 树）。
**所以对于解决模式串类的问题，AC 自动机的本质就是对于每一种字符串，除了记录在它后面加字符能到达的出现过的串（$Trie$ 树），还记录了在它前面加字符能到达的出现过的串（$fail$ 树）。**
**那么对于 $s$ 串的子串信息，我们可以对 $s$ 的前缀跳 $fail$ 链。而对于 $t$ 串的扩展串信息（$t$ 是某个串的子串），我们可以在 $fail$ 树中遍历 $t$ 树的子树，再在 $Trie$ 树中遍历 遍历到的点 的子树。**
#### 例题
1.请你分别求出每个模式串 $T_i$ 在文本串 $S$ 中出现的次数。
可以直接按我们刚刚的做法来做（跳 $S$ 前缀的 $fail$ 链），但是会 T 飞。
考虑优化，把根到 $S$ 路径上的节点都标记（设为 $size=1$），然后建立 $fail$ 树（$fail_i \to i$），设 $size_i$ 为 $i$ 这个节点所代表的字符串在 $S$ 中出现的次数。
那么在 $fail$ 树中，$i$ 的子树中的所有有效节点都能为 $size_i$ 贡献 $1$。所以把每一个有效节点 $size$ 的初始值都设为 $1$ 然后在 $fail$ 树上从下往上统计 $size$。
（其实这里有些地方写的东西并不严谨（详见代码），主要是我现在有一些地方还没理解透彻，等到时候理解了之后再补吧）
```cpp
#include<bits/stdc++.h>
#define N 200010
#define ll long long
using namespace std;
struct Trie
{
int ch[26],fail;
ll size;
}t[N];
int n,node,id[N];
int cnt,head[N],nxt[N],to[N];
void adde(int u,int v)
{
to[++cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
}
int insert(string s)
{
int u=0,len=s.size();
for(int i=0;i<len;i++)
{
int v=s[i]-'a';
if(!t[u].ch[v]) t[u].ch[v]=++node;
u=t[u].ch[v];
}
return u;
}
void dfsTrie(string s)
{
int u=0,len=s.size();
for(int i=0;i<len;i++)
{
int v=s[i]-'a';
u=t[u].ch[v];//主要是这里理解的不是很透彻，如果此时u没有v这个转移，那么这条语句会自动让u回到根重新开始，那这样就有点奇怪了
t[u].size++;
}
}
void getfail()
{
queue<int>q;
for(int i=0;i<26;i++)
if(t[0].ch[i])
q.push(t[0].ch[i]);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=0;i<26;i++)
{
if(t[u].ch[i])
{
t[t[u].ch[i]].fail=t[t[u].fail].ch[i];
q.push(t[u].ch[i]);
}
else t[u].ch[i]=t[t[u].fail].ch[i];
}
}
for(int i=1;i<=node;i++)
adde(t[i].fail,i);
}
void dfsFail(int u)
{
for(int i=head[u];i;i=nxt[i])
{
int v=to[i];
dfsFail(v);
t[u].size+=t[v].size;
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
string str;
cin>>str;
id[i]=insert(str);
}
getfail();
string s;
cin>>s;
dfsTrie(s);
dfsFail(0);
for(int i=1;i<=n;i++)
printf("%lld\n",t[id[i]].size);
return 0;
}
/*
3
abc
cde
de
abcde
*/
```
2.https://blog.csdn.net/ez_lcw/article/details/99613063
# 后缀自动机（SAM）
## 大概流程
（以下的 “节点” 均表示后缀自动机中的节点）
（定义对于两个字符串 $A,B$ 的运算 $A+B$ 表示 $A$ 和 $B$ 顺次拼接起来的串）
（下面请注意 $S(i)$ 和 $S[i]$ 的区别，其中后者表示字符串 $S$ 的第 $i$ 位，而前者在下文中会有定义）
### $\operatorname{Endpos}$ 集合
我们把 $S$ 的一个子串在 $S$ 中每一次出现的结束位置的集合定义为 $\operatorname{Endpos}$ 集合。
然后我们考虑我们要构建的后缀自动机长什么样：我们将 $\operatorname{Endpos}$ 集合完全相同的子串合并到同一个节点。
我们发现，对于越短的子串，其 $\operatorname{Endpos}$ 集合往往越大。更具体地，如果 $t$ 是某一个子串 $T$ 的后缀，则 $|\operatorname{Endpos}(t)|\geq |\operatorname{Endpos}(T)|$。当且仅当取等号时，$t$ 和 $T$ 会被压缩到同一个节点中。
而对于某一个子串 $T$ 来说，肯定有一个分界长度 $len$，使得每一个长度 $\geq len$ 的 $T$ 的后缀的 $\operatorname{Endpos}$ 都和 $\operatorname{Endpos}(T)$ 相同（所以这些后缀和 $T$ 在同一个节点），且每一个长度 $<len$ 的 $T$ 的后缀的 $\operatorname{Endpos}$ 大小都比 $\operatorname{Endpos}(T)$ 大（所以这些后缀和 $T$ 不在同一个节点，而且这些后缀可能在不同的节点）。
所以每个节点 $u$ 中存储的一定是一堆长度连续的子串，且短的串是长的串的后缀。不妨把这些串的集合称为 $S(u)$，设其中最长的串为 $\operatorname{longest}(u)$，最短的串为 $\operatorname{shortest}(u)$。
我们在具体实现时会用一个 $len$ 数组记录每个节点中最长的子串的长度（即 $\operatorname{longest}(u)$ 的长度），为什么不用记最短的长度，下文会讲。
### Parent Tree
如上文所述，对于每一个子串都会有唯一一个 ”分界长度“，而且每一个节点中所有子串的 “分界长度” 都相同，为这个节点中最短的子串的长度。
而如果 $t$ 是 $T$ 的一个后缀且没有和 $T$ 分在一个节点中，那么 $t$ 肯定也是别的子串的后缀，例如 $\texttt{ab}$ 在串 $\texttt{cabzab}$ 中既可以是 $\texttt{cab}$ 的后缀，也可以是 $\texttt{zab}$ 的后缀。这样我们看到：长的串 $T$ 只能 “对应” 唯一的一个短的串 $t$，而短的串可以 “对应” 多个长的串，如果将 “短的串” 视为 “长的串” 的父亲，这就构成了一棵严格的树形结构。我们称为Parent Tree。
形式化地说，对于一个节点 $u$，我们找到 $S(u)$ 中某一个子串 $T$ 的后缀 $t$，使得 $t$ 不在 $\operatorname{S}(u)$ 中且满足 $|t|$ 最大（显然 $t$ 是 $S(u)$ 中任何一个串的后缀且 $|t|$ 等于 $S(u)$ 中任何一个串的 “分界长度“ 减 $1$），记 $u$ 的后缀链接 $\operatorname{link}(u)$ 为 $t$ 所属的节点。那么 $\operatorname{link}$ 所构成的就是这个 Parent Tree。
这时你会发现 $\operatorname{shortest}(u)$ 的长度其实就是 $\operatorname{longest}(\operatorname{link}(u))$ 的长度加 $1$，即 $len(\operatorname{link}(u))+1$，所以我们无需记录 $\operatorname{shortest}(u)$ 的长度。
### SAM 的转移
对于一个节点 $u$，在 $S(u)$ 中的某一个串后面添加一个字符 $c$ 变成一个新的串，如果这个新的串仍是 $S$ 的子串
（那么显然此时 $S(u)$ 中的所有串添加这个字符 $c$ 所形成的的新串也都仍是 $S$ 的子串${\,}^{(1)}$），设这个新串所属的节点为 $p$，那么我们记录转移 $ch[u][c]\gets p$。
注意对于添加字符 $c$ 而言，添加后的新串可能不同，但可以证明它们都是属于同一个等价类的，也就是它们所属的节点都是相同的，也就是说 $ch[u][c]$ 是唯一的${\,}^{(2)}$。
### 算法（实现）
考虑从前往后插入 $S$ 的每一个字符，假设当前插入的是 $c=S[x]$。
那我们肯定要先新建一个节点 $now$ 表示 $S[1..x]$ 的 $\operatorname{Endpos}$ 等价类，因为这个等价类之前一直没有出现过。
我们上一次插入 $S[x-1]$ 的时候肯定也新建了一个节点表示 $S[1..x-1]$ 的 $\operatorname{Endpos}$ 等价类，记这个节点为 $last$。
那么显然有 $ch[last][c]=now$。
进一步，我们发现 $last$ 在 Parent Tree 上的祖先似乎也都可以转移到 $now$。
不妨令 $p=last$，然后让 $p$ 沿着 $\operatorname{link}$ 往上跳，并且一直记录 $ch[p][c]\gets now$，直到满足已经存在转移 $ch[p][c]$ 了（此时证明 $S[1..x-1]$ 中出现过 $S[1..x]$ 的后缀）。
这样做肯定是对的，因为让 $p$ 一直往上跳的过程相当于从长到短枚举 $S[1..x-1]$ 后缀中的每一种 $\operatorname{Endpos}$ 定价类，也就相当于把 $S[1..x-1]$ 的所有后缀都枚举一遍，而判断是否已经存在转移 $ch[p][c]$ 也就相当于把 $S[1..x]$ 的每一个后缀都枚举了一遍（因为满足一个串 $T$ 是 $S[1..x]$ 的后缀的必要条件是 $T$ 去掉最后一位后是 $S[1..x-1]$ 的后缀），并判断它们是否在 $S[1..x-1]$ 中出现过。
我们分情况讨论：
- 如果就这么顺着 Parent Tree 跳一直跳到了根节点还要往上，此时证明 $S[1..x-1]$ 中没有串和 $S[1..x]$ 的任何一个后缀相等，所以 $S[1..x]$ 的每一个后缀的 $\operatorname{Endpos}$ 都是相同的，所以我们直接让 $\operatorname{link}(now)=rt$。
- 否则，如果我们在跳的过程中找到了一个 $p$ 使得已经存在转移 $ch[p][c]$ 了，我们就先设 $q=ch[p][c]$。
那我们就看 $S(q)$ 中的任何一个串是否都能等于 $S[1..x]$ 的某一个后缀。
其实也就是要看 $\operatorname{longest}(q)$ 是否等于 $S[1..x]$ 的某一个后缀，因为 $S(q)$ 中的其他串都是 $\operatorname{longest}(q)$ 的后缀。
发现 $\operatorname{longest}(q)$ 能和 $S[1..x]$ 的某一个后缀相等当且仅当 $len(q)=len(p)+1$。
> 证明：
>
> 首先显然有 $len(q)$ 不可能小于 $len(p)+1$，因为串 $\operatorname{longest}(p)+c$ 属于 $q$（原因上面 $(2)$ 处有提到），所以 $len(q)\geq |\operatorname{longest}(p)+c|=len(p)+1$。
>
> 其次，如果 $len(q)>len(p)+1$，且 $\operatorname{longest}(q)$ 和 $S[1..x]$ 的某一个后缀相等，那么我们去掉 $\operatorname{longest}(q)$ 末尾的 $c$ 得到一个新串（其长度为 $len(q)-1$），这个新串显然也和 $S[1..x-1]$ 的某一个后缀相等。又由于之前一直不存在转移 $ch[p][c]$，所以这个新串所属的节点只能为 $p$。而这个新串的长度为 $len(q)-1>len(p)$，矛盾。
>
> 所以 $\operatorname{longest}(q)$ 能和 $S[1..x]$ 的某一个后缀相等当且仅当 $len(q)=len(p)+1$。
然后我们再分情况讨论：
- 若 $len(q)=len(p)+1$，此时 $S(q)$ 中的任何一个串都是 $S[1..x]$ 的某一个后缀，我们直接令 $\operatorname{link}(now)\gets q$ 即可。
可以证明这样找到的 $q$ 一定是最长的，因为我们是从长到短枚举的 $S[1..x-1]$ 后缀中的每一种 $\operatorname{Endpos}$ 定价类，也就是说我们是从长到短枚举的 $S[1..x-1]$ 的所有后缀，那么此时找到的 $q$ 一定是最长的。
- 若 $len(q)\neq len(p)+1$，此时 $\operatorname{longest}(q)$ 不是 $S[1..x]$ 的后缀，而且 $\operatorname{longest}(q)$ 会比 $\operatorname{longest}(p)$ 长一截。
那么此时 $\operatorname{longest}(q)$ 的一部分长的后缀（即 $S(q)$ 中除了 $S(p)+c$ 的那一部分串）仍不是 $S[1..x]$ 的后缀，而 $\operatorname{longest}(q)$ 的一部分短的后缀（即 $S(q)$ 中与 $S(p)+c$ 相等的那一部分串）成为了 $S[1..x]$ 的后缀，这两部分串的 $\operatorname{Endpos}$ 等价类已经不同了，所以它们不能待在同一个节点，必须得分离。
于是我们新建一个点 $nq$，表示 $S(q)$ 中与 $S(p)+c$ 相等的那一部分串的 $\operatorname{Endpos}$ 等价类。这样就在 $q$ 和 $f=\operatorname{link(q)}$ 之间新插入了一个点，所以 $\operatorname{link}(q)\gets nq$，$\operatorname{link}(nq)\gets f$。同时注意更新 $len(nq)\gets len(p)+1$，$ch[nq]\gets ch[q]$（更新 $ch[nq]\gets ch[q]$ 的原因上面 $(1)$ 处有提到）。
注意要让 $\operatorname{link}(now)\gets nq$，证明 “这样找到的 $nq$ 一定是最长的” 的过程同上面那种情况。
最后，我们就要更新我们还要继续让 $p$ 沿着 $\operatorname{link}$ 往上跳，如果 $ch[p][c]=q$，那么更新 $ch[p][c]\gets nq$（这里这么更新的证明比较显然，略去），否则停止上跳退出。
这样 SAM 就建好了。
## 实际应用
咕咕咕……