后缀自动机（个人笔记）
柒葉灬
2019-04-18 20:44:21
# 后缀自动机
------
具体原理就不多叙述了，网上已经很清楚了。
-----------
#### 模板
```cpp
struct node{
int son[26],len,fa;
void clear(){
memset(son,0,sizeof(son));
len=fa=0;
}
}t[maxn<<1];
void extend(int c){
int p=last,np=last=++tot;
t[np].clear();
t[np].len=t[p].len+1;
while(p&&!t[p].son[c])t[p].son[c]=np,p=t[p].fa;
if(!p)t[np].fa=1;
else {
int q=t[p].son[c];
if(t[q].len==t[p].len+1)t[np].fa=q;
else {
int nq=++tot;
t[nq]=t[q];t[nq].len=t[p].len+1;
t[q].fa=t[np].fa=nq;
while(p&&t[p].son[c]==q)t[p].son[c]=nq,p=t[p].fa;
}
}
}
```
------
#### 一句话题解系列（雾）：
[专题A](https://cn.vjudge.net/contest/287949#problem/A)
每一次询问的时候重新在$[l,r]$区间内建$SAM$
看似很暴力，实则复杂度是对的，
**记住SAM建立的复杂度是$O(n)$的。**
-------------
[专题B](https://cn.vjudge.net/contest/287949#problem/B)
题意：有多少个是字符串A的子串，但不是字符串Bi的子串。
输入Bi串的时候跑一遍自动机，标记每个点可延伸最长的子串
合法串的个数就是$max(0,t[x].len-max(Max[x],t[f].len))$
拓扑排序把最大值贡献给父亲，
---------
[专题C](https://cn.vjudge.net/contest/287949#problem/C)
**题意：查找两个串的最长公共子串**
对着一个建SAM，然后另一个串跑自动机，
如果$trans$指向的点为0时，跳slink数组，
然后更新当前匹配长度，$len=t[x].len$
可以发现，这跳slink的操作就像跳fail数组一样，
答案就是len的最大值。
（不知道为什么强行把$last=1$会对）
----------
[专题D](https://cn.vjudge.net/contest/287949#problem/D)
题意：给n个串，输出询问串有多少个与其有相同endpos的串
每两个串之间插入一个从未出现过的字符，
求出每个节点的最小len值，防止有特殊字符串被计入答案。
------
[专题E](https://cn.vjudge.net/contest/287949#problem/E)
题意：求有多少个子串出现至少两次，且两次不重叠。
算每一个节点endpos的最大值和最小值，
计算每一个节点贡献子串就行了。
[专题F](https://cn.vjudge.net/contest/287949#problem/F)
题意：求有多少个子串出现恰好$K$次。（水题）
每个节点出现个数就是endpos的个数，
拓扑排序收集个数即可
[专题G](https://cn.vjudge.net/contest/287949#problem/G)
**题意：有多少个子串出现至少$K$次，有加字符操作**
离线，建一个完整的SAM，
算每一个节点第K个endpos的位置，
需要用到**线段树合并**
每一次计算之后合并到父亲即可，不需要可持久化。
-------
[专题H](https://cn.vjudge.net/contest/287949#problem/H)
_~~题意：详见后缀数组专题的翻译（233）~~_
对串反向建SAM，维护每一个节点最小的endpos
记录下每一个后缀的对应的节点，
倍增跳fa,找到第一个mn小于当前x的节点，len就是最大lcp
----------
[专题I](https://cn.vjudge.net/contest/287949#problem/I)
### （难题）
**题意：从A中取一个子串x，B中取一个子串y，问x+y可以形成多少不同的新串（x，y均可以为空串）**
这题最麻烦的就是会有重复的，即使$x!=x',y!=y'$，也有可能出现$x+y==x'+y'$
为了防止这种情况出现，可以使取出的x尽可能长，
即，x加上y的第一个字符**不属于A的子串**
最终得到：扫一遍A的SAM，若trans(x,i)==NULL，
则判断B当中以i为开始有多少不同子串即可，
最后在特殊处理一下空串的情况就能A了。
-----------
[专题J](https://cn.vjudge.net/contest/287949#problem/J)
### （好题）
**题意：给一个目标串。每次有两种操作：**
**1.在当前串后面加字符，代价为对应字符的成本cost[i]**
**2.选则一段长度len的子串，复制到后面，花费A\*len+2*B**
**初始为空串，问达到目标串的最小代价。**
这题显然是需要dp的，每次转移时重点就在操作2上，
可以发现，只要知道最远能从哪里转移就行了，
区间求min，**用树状数组维护最小值，倍增维护最远点。**
### 补充：
这题可以在线建立着一个SAM，
使得这个SAM的长度就是上面提到的需要维护的最小值$j$，
如果不能匹配了就$extend(str[++j])$
直到能够匹配或者$i==j$
复杂度从$O(nlogn)$到$O(n)$
-----------------