后缀自动机学习笔记(应用篇)
command_block
2019-07-06 14:30:06
请配合 [后缀自动机学习笔记(干货篇)](https://www.luogu.org/blog/command-block/hou-zhui-zi-dong-ji-xue-xi-bi-ji) 与 [题单:SAM练习题](https://www.luogu.com.cn/training/5322) 食用。
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
------
# 4. $\rm SAM$ 的初级应用
历经千辛万苦构造出了 $\rm SAM$ ,它能干什么呢?
- $\color{blue}\bf \Delta 4.1$ **解决单文本多次匹配的问题**
众所周知, $\rm SAM$ 是一个能够匹配所有子串的自动机。
首先建立出文章串的 $\rm SAM$ ,按照自动机的定义直接匹配即可,复杂度$O(n+m)$,$m$是询问串总长。
代码就不放了,毕竟太模板了……
- $\color{blue}\bf \Delta 4.2$ [**P2408 不同子串个数**](https://www.luogu.org/problemnew/show/P2408)
比较套路的一道题目。
- **思路1**: $\rm SAM$ 是个`DAG`,于是乎可以在上面`DP`。(不常用)
一般来讲,`DAG`上可能重复转移,是很难跑计数`DP`的。
但是我们知道后缀自动机的性质 : 任意两个节点的表示集合没有交。
所以,从某个节点(不一定要求是源点)出发的路径组成的串,都是互不相同的,如果相同的话,就违背了上述性质。
所以我们只要统计路径数即可,不需要考虑重复问题。
设 $f[u]$ 表示从 $u$ 出发的路径数,包括从 $u$ 到 $u$ (空串)。
`DP`的时候令 $f[u]+=f[son]$ 即可,最后还要加上自己到自己的 $1$。
不过题目中不算空串,那么 $f[1]-1$ 就是答案。
**Code:**
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define MaxN 100500
using namespace std;
int n;
char str[MaxN];
struct Node
{int t[26],f,len;}
a[MaxN<<1];
int las,tn;
void add(int c)
{
int p=las,np=++tn;las=np;
a[np].len=a[p].len+1;
for (;p&&!a[p].t[c];p=a[p].f)a[p].t[c]=np;
if (!p)a[np].f=1;//case 1
else {
int v=a[p].t[c];
if (a[v].len==a[p].len+1)a[np].f=v;//case 2
else {
int nv=++tn;a[nv]=a[v];
a[nv].len=a[p].len+1;
for (;p&&a[p].t[c]==v;p=a[p].f)a[p].t[c]=nv;
a[np].f=a[v].f=nv;//case 3
}
}
}
long long f[MaxN<<1];
void dfs(int u)
{
if (f[u])return ;
for (int i=0,v;i<26;i++)
if (v=a[u].t[i])
{dfs(v);f[u]+=f[v];}
f[u]++;
}
int main()
{
scanf("%d%s",&n,str);las=tn=1;
for (int i=0;i<n;i++)add(str[i]-'a');
dfs(1);
printf("%lld",f[1]-1);
return 0;
}
```
- **思路2**: $\rm SAM$ 每个节点表示的串没有交集,而且一定表示了所有的串。
那我们把所有节点表示的串的个数(类大小)加起来就好了,
考虑到 $minlen(u)=maxlen(fa)+1$ ,我们统计 $\sum\limits_{u}(u.len-u.fa.len)$即可。
这种方法需要对 $\rm SAM$ 的基本性质比较熟悉,同时也很经典,建议好好理解。
**Code:**
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define MaxN 100500
using namespace std;
int n;
char str[MaxN];
struct Node
{int t[26],f,len;}
a[MaxN<<1];
int las,tn;
void add(int c)
{
int p=las,np=++tn;las=np;
a[np].len=a[p].len+1;
for (;p&&!a[p].t[c];p=a[p].f)a[p].t[c]=np;
if (!p)a[np].f=1;//case 1
else {
int v=a[p].t[c];
if (a[v].len==a[p].len+1)a[np].f=v;//case 2
else {
int nv=++tn;a[nv]=a[v];
a[nv].len=a[p].len+1;
for (;p&&a[p].t[c]==v;p=a[p].f)a[p].t[c]=nv;
a[np].f=a[v].f=nv;//case 3
}
}
}
int main()
{
scanf("%d%s",&n,str);las=tn=1;
for (int i=0;i<n;i++)add(str[i]-'a');
long long ans=0;
for (int i=1;i<=tn;i++)ans+=a[i].len-a[a[i].f].len;
printf("%lld",ans);
return 0;
}
```
- $\color{blue}\bf \Delta 4.3$ [**P3804 【模板】后缀自动机**](https://www.luogu.org/problemnew/show/P3804)
我们知道每个点代表着一个 $\rm edp$ 等价类。
显然有 : $\rm edp$ 集合大小 (比较常用,后面称为 `siz` ) 就是这点包含的一堆字子串(在原串中)的**出现次数**。
如何统计 `siz` 呢?我们考虑$\rm parent$树上一遍树形`DP`:
先把**每个前缀所属的点**的 `siz` 设为$1$,可以证明这些点是前缀对应的 $\rm edp$ 出现的$\rm parent$树上最深的点,因为无法在这些前缀前面加东西。
称这些点为**前缀节点**,每个前缀节点代表一个 $\rm edp$。
( 事实上,有且仅有某个前缀节点的祖先拥有该 $\rm edp$,这在后面会详细讲 )
然后 `u.siz+=son.siz` ,子树求和即可。
> 这需要把树建出来,常数较大。
> 另外一种常数更小的方法是:先按照`len`排序,然后`len`大的先贡献。
> 由于 $fa.len>u.len$ 正确性显然。
> 这个排序如果用 `std::sort` 的话复杂度反而会带 $log$ ,那就得不偿失了。
> 观察到所有的 $len\leq n$ ,不妨使用基数排序。
> 但是这种方法有一定的局限性,比如说广义 $\rm SAM$ 用不了,某些时候操作麻烦等等……
我们也维护了某个点的最长串 `len` ,统计 $\max\limits_u[u.siz<1](u.siz*u.len)$ 即可。
**Code:**
这里只提供树形dp版,基排版可以到其他题目里面找。
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define ll long long
#define MaxN 1005000
using namespace std;
struct Node
{int t[26],f,len,siz;}
a[MaxN<<1];
int tn,las;
void add(int c)
{
int p=las,np=++tn;las=np;
a[np].len=a[p].len+1;
for (;p&&!a[p].t[c];p=a[p].f)a[p].t[c]=np;
if (!p)a[np].f=1;
else {
int v=a[p].t[c];
if (a[v].len==a[p].len+1)a[np].f=v;
else {
int nv=++tn;a[nv]=a[v];
a[nv].len=a[p].len+1;
for (;p&&a[p].t[c]==v;p=a[p].f)a[p].t[c]=nv;
a[np].f=a[v].f=nv;
}
}
}
vector<int> g[MaxN<<1];
ll ans;
void dfs(int u)
{
for (int i=0,v;i<g[u].size();i++){
dfs(g[u][i]);
a[u].siz+=a[g[u][i]].siz;
}
if (a[u].siz>1)
ans=max(ans,1ll*a[u].siz*a[u].len);
}
int n;
char str[MaxN];
int main()
{
scanf("%s",str+1);
n=strlen(str+1);
las=tn=1;
for (int i=1;i<=n;i++)add(str[i]-'a');
for (int i=1,p=1;i<=n;i++){
p=a[p].t[str[i]-'a'];
a[p].siz=1;
}for (int i=2;i<=tn;i++)
g[a[i].f].push_back(i);
dfs(1);
printf("%lld\n",ans);
return 0;
}
```
- $\color{blue}\bf \Delta 4.4$ [**CF802I Fake News (hard)**](https://www.luogu.org/problem/CF802I)
首先这个翻译非常的假,人话题意:本质不同子串出现次数的平方和
对于 $\rm SAM$ 上的节点,计算$\sum\limits_{u}u.siz^2*(u.len-fa.len)$即可。
[评测记录](https://www.luogu.org/record/22924038)
- $\color{blue}\bf \Delta 4.5$ [**P4070 [SDOI2016]生成魔咒**](https://www.luogu.org/problemnew/show/P4070)
**题意** : 不断`push_back`字符,每次统计本质不同子串数。
( 这道题字符集很大,需要使用 `std::map` 建立后缀自动机 )
上文$4.2$中,我们讲到 $ANS=\sum\limits_{u}(u.len-u.fa.len)$
那么每次有 $len$ 变化的时候,维护这个总和就好了。
首先新建 `np` 的时候,`ans+=a[np].len;`
然后对于`case 1,2`,我们没有新建节点,只是加入了一条`f`指针,所以`ans-=a[a[np].f].len`
对于`case 3`,我们新建了 `nv` ,要使`ans+=a[nv].len;`,
但是它只有两个儿子 `v` 和 `np` ,又需要`ans-=2*a[nv].len;`
又考虑到`a[np].f=nv`,其实还是`ans-=a[a[np].f].len;`
综上,每次`add`之后令`ans+=a[np].len-a[a[np].f].len;`即可。
[评测记录](https://www.luogu.org/record/20356453)
- $\color{blue}\bf \Delta 4.6$ **字典序第 k 小子串**
[P3975 [TJOI2015]弦论](https://www.luogu.org/problemnew/show/P3975)
细节比较的多TAT
我们考虑使用类似线段树上二分的办法,在 $\rm SAM$ 上跳(建议结合代码理解)。
已经到达了某个点,我们从 `a~z` 枚举出边,选定后,当前剩余的 $k$ 要减去字典序比当前构造串小的串的个数。
注意在开始选择路径之前,还得要减去一些东西(详见代码)……
问题就在于减掉多少。设 $f[u]$ 表示从 $u$ 出发能得到的字符串个数。
- $t=0$ ,本质相同子串只算一次
这很好办, $f[u]=$从该点出发的路径总条数,这个按照$4.2.1$`dp`出来。
- $t=1$ ,本质相同子串算多次
开始麻烦了……我们知道一个子串 $s$ 的出现次数$={\rm edp}(s)$
那么我们就是要统计`DAG`上 $u$ 的一颗子`DAG`内, $\sum\limits_{path:u\rightarrow v}v.siz$
也就是每一个串(路径)的贡献是 : 终点的 $|edp|$ ,即`siz`。
采用$4.3$的方法计算`siz`即可。
那么如何统计呢?这也好办,$4.2.1$中空串的贡献是$1$,现在改成`siz`就可以了。
如何判断无解?这道题同样不计空串,我们要在 $f[1]$ 内把空串的贡献去掉,然后 $f[1]<k$ 即无解(一共没有 $k$ 个满足题意的子串)。
注意其他点空串的贡献是不能去掉的,因为空串表示停止在该点。
[评测记录](https://www.luogu.com.cn/record/20358450)
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
------
# 5. $\rm SAM$ 与AC自动机的相似性
回忆 : 自动机某个点表示的串,是指从根到该点的路径构成的所有串。
众所周知,AC自动机的 `fail` 指针指向的地方,是该节点表示的串的最长后缀,也就是把前面去掉(尽可能少的)一点。
我们注意到 $\rm SAM$ 的`fa`指针有同样的性质 : 儿子是由父亲在前面加字符产生的,那么父亲就可以视作在儿子前面去掉字符。
我们完全可以把 $\rm SAM$ 理解为把某个串的**所有子串建立AC自动机**。
这有什么用呢? 来看一下例题吧:
- $\color{blue}\bf \Delta 5.1$ [**SP1811 LCS - 最长公共子串**](https://www.luogu.org/problem/SP1811)
我们把两个串分别称作 $S1,S2$.
对于 $S2$ 设一个数组为 $slen[1...|S2|]$.
$slen[i]$ 表示 $S1$ 中 $S1[i-slen[i]+1,i]$ 在 $S2$ 中出现过,即以 $i$ **结尾**的位置的**最长匹配长度**。
即“每个前缀匹配出的最长后缀”,不难发现, $slen$ 数组的 $\max$ 就是答案。
怎么求呢?对 $S1$ 建立 $\rm SAM$ ,然后当做AC自动机来用。
把 $S2$ 拿到上面跑匹配,如果当前节点有出边,则匹配长度++
否则,跳`fail`直到有出边为止,匹配长度变为该点的`len+1`。
如果回到根还是不能匹配,匹配长度是 $0$.
(具体见代码)
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#define MaxN 250500
using namespace std;
struct Node
{int t[26],f,len;}a[MaxN<<1];
int tn,las;
void add(int c)
{
int np=++tn,p=las; las=np;
a[np].len=a[p].len+1;
for (;p&&!a[p].t[c];p=a[p].f)a[p].t[c]=np;
if (!p)a[np].f=1;
else {
int v=a[p].t[c];
if (a[p].len+1==a[v].len)a[np].f=v;
else {
int nv=++tn; a[nv]=a[v];
a[nv].len=a[p].len+1;
for (;p&&a[p].t[c]==v;p=a[p].f)a[p].t[c]=nv;
a[v].f=a[np].f=nv;
}
}
}
int slen[MaxN],len1,len2;
char s1[MaxN],s2[MaxN];
int main()
{
scanf("%s%s",s1,s2);
len1=strlen(s1);len2=strlen(s2);
tn=las=1;
for (int i=0;i<len1;i++)add(s1[i]-'a');
//构造 $\rm SAM$
int p=1,plen=0;//当前点,匹配长度
for (int i=0,c;i<len2;i++){
c=s2[i]-'a';
if (!a[p].t[c]){
while(p!=1&&!a[p].t[c])p=a[p].f;
plen=a[p].len;
//如果没有转移边,不断跳fail
}
if (a[p].t[c]){
p=a[p].t[c];plen++;
//能匹配,plen++
}slen[i]=plen;
}
int ans=0;
for (int i=0;i<len2;i++)ans=max(ans,slen[i]);
printf("%d",ans);
return 0;
}
```
## 5.2 [SP1812 LCS2 - 多串最长公共子串](https://www.luogu.org/problem/SP1812)
类似地,把第一个串当做匹配串,其他的串建立 $\rm SAM$
把第一个串在每个 $\rm SAM$ 上跑匹配,$slen$ 对当前匹配长度取$\min$。
最终回答整个 $slen$ 的 $\max$。
代码奇短无比,比SA+单队不知高到哪里去了。
[AC记录](https://www.luogu.org/record/22923336)
## 5.3 [CF235C Cyclical Quest](https://www.luogu.org/problem/CF235C)
题意 : 给出一个文本串和若干询问串,求每个询问串的所有本质不同循环,能够匹配到的次数。
先不考虑本质不同这件事。
循环就是把询问串第一个字符拿去放在最后面。
可以视为,先把目前匹配到的串的第一个字符删掉,然后再加上一个。
如果目前这个串根本没有在文本中完整出现,那么这个删除操作可以忽略。
否则,`len--`,如果删了前面之后 $len$ **不在当前节点区间**($(u.fa.len,u.len]$)里面了就跳 `f`。
(在前面删掉字符?这不就是parent tree跳`f`的性质吗!)
加字符的操作同上。
(~~太有趣了,双端队列?很有出题价值![笑]~~)
最后把匹配到的所有节点 $siz$ 加在一起就好了。
还要考虑去重问题,这也好办 : 如果同一个询问串多次匹配到同一个节点,贡献只算一次,具体可以打标记实现。
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define MaxN 1000500
using namespace std;
struct Node
{int t[26],len,f,siz;}a[MaxN<<1];
int tn,las;
void add(int c)
{
int p=las,np=++tn; las=np;
a[np].len=a[p].len+1;
for (;p&&!a[p].t[c];p=a[p].f)a[p].t[c]=np;
if (!p)a[np].f=1;
else {
int v=a[p].t[c];
if (a[v].len==a[p].len+1)a[np].f=v;
else {
int nv=++tn;a[nv]=a[v];
a[nv].len=a[p].len+1;
for (;p&&a[p].t[c]==v;p=a[p].f)a[p].t[c]=nv;
a[np].f=a[v].f=nv;
}
}
}
vector<int> g[MaxN<<1];
void dfs(int num)
{
for (int i=0;i<g[num].size();i++){
dfs(g[num][i]);
a[num].siz+=a[g[num][i]].siz;
}
}
char str[MaxN];int len;
int vis[MaxN<<1],T;
void solve()
{
scanf("%s",str+1);
len=strlen(str+1);
int slen=0,p=1;
for (int i=1;i<=len;i++){
str[i]-='a';
while(p>1&&!a[p].t[str[i]])
slen=a[p=a[p].f].len;
if (a[p].t[str[i]]){
p=a[p].t[str[i]];
slen++;
}
}long long ans=0;
for (int i=1;i<=len;i++){
if (slen==len){
if (vis[p]!=T)ans+=a[p].siz;
vis[p]=T;
if (--slen==a[a[p].f].len)
p=a[p].f;
}while(p>1&&!a[p].t[str[i]])
slen=a[p=a[p].f].len;
if (a[p].t[str[i]]){
p=a[p].t[str[i]];
slen++;
}
}printf("%I64d\n",ans);
}
int main()
{
scanf("%s",str+1);
len=strlen(str+1);
tn=las=1;
for (int i=1;i<=len;i++)add(str[i]-='a');
for (int i=2;i<=tn;i++)g[a[i].f].push_back(i);
for (int i=1,p=1;i<=len;i++)
a[p=a[p].t[str[i]]].siz=1;
dfs(1);
scanf("%d",&T);T++;
while(--T)solve();
return 0;
}
```
## 5.4 [P6640 [BJOI2020] 封印](https://www.luogu.com.cn/problem/P6640)
先建立 $S$ 的 $\rm SAM$ ,然后让 $T$ 在上面跑匹配,求出 $T$ 的每个前缀 $i$ 能够匹配的后缀长度 $sl[i]$。
对于区间 $[l,r]$ 的限制,答案是 $\max\limits_{i=l}^r\min(sl[i],i-l+1)$。
可以二分答案 $mid$ , 然后 $i$ 必须满足 $i-l+1\geq mid$ 即 $i\geq mid+l-1$。
若满足这个要求,那么 $i+l+1$ 的约束就可以不考虑了,变成一个区间 $\max$ 问题,可以用 $ST$ 表做到 $O(1)$。
复杂度 $O(n\log n)$。[评测记录] ()
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
------
# 6. $\rm SAM$ 构建后缀树
$\rm SAM$ 并不是万能的,有些时候使用后缀数据结构家族的另两个成员 : 后缀树/后缀数组 才能够更快更好地解决问题。
问题在于,同时掌握这三个东西也太麻烦了趴!!! 而且 $\rm SAM$ 代码又短又简洁,用惯了就容易忘掉其他的东西……
万幸的是,有用 $\rm SAM$ 来构造后缀树的方法,真是造(bao)福(fu)社会啊!
有一个很好用的结论:**反串的 $\rm SAM$ 的parent树就是后缀树**。
严谨证明的话咱这里没有……但是可以感性理解 :
parent树有一个性质,父亲是孩子的最长后缀( $\rm edp$ 不同)。
而把串翻转过来之后,反串的parent树就满足 : 父亲是孩子的最长前缀 ( $beginpos$ 不同 )。
观察压缩后缀树的定义, $\rm bgp$ 相同的两个串才能被压缩,所以 $\rm SAM$ 和后缀树其实是有异曲同工之妙的!
另一个构造后缀树的算法是Ukk,复杂度同样要依赖字符集大小,因此, $\rm SAM$ 构造法几乎可以完全替代Ukk。(naive了,花样其实还有很多)
这里还要讲一些性质。
- 设 $lcs(i,j)$ 为前缀 $i,j$ 的最长公共后缀长度,其等于$\rm parent$树上 `LCA` 的 $len$ 值。
**例题** : [P4248 [AHOI2013]差异](https://www.luogu.org/problem/P4248)
这道题可以转化为求两两后缀的 $lcp$ 和。
众所周知,这就相当于求后缀树上两两叶节点的 $lca$ 深度总和。
建立后缀树之后,写一个树形dp就可以搞定了:
**Code:**
```cpp
#include<cstring>
#include<vector>
#include<cstdio>
#define MaxN 500500
using namespace std;
struct Node
{int t[26],f,len;}a[MaxN*2];
int tn,las;
void add(int c)
{
int np=++tn,p=las; las=np;
a[np].len=a[p].len+1;
for (;p&&!a[p].t[c];p=a[p].f)a[p].t[c]=np;
if (!p)a[np].f=1;
else {
int v=a[p].t[c];
if (a[p].len+1==a[v].len)a[np].f=v;
else {
int nv=++tn; a[nv]=a[v];
a[nv].len=a[p].len+1;
for (;p&&a[p].t[c]==v;p=a[p].f)a[p].t[c]=nv;
a[v].f=a[np].f=nv;
}
}
}
long long sum;
int siz[MaxN*2];
vector<int> g[MaxN*2];
void dfs(int num)
{
int sav=siz[num];
for (int i=0;i<g[num].size();i++){
dfs(g[num][i]);
siz[num]+=siz[g[num][i]];
}
for (int i=0;i<g[num].size();i++)
sum+=1ll*siz[g[num][i]]*(siz[num]-siz[g[num][i]])*a[num].len;
sum+=1ll*sav*(siz[num]-sav)*a[num].len;
}
char str[MaxN];int len;
int main()
{
scanf("%s",str);len=strlen(str);
las=tn=1;
for (int i=len-1;i>=0;i--)add(str[i]-'a');
for (int i=len-1,p=1;i>=0;i--){
p=a[p].t[str[i]-'a'];
siz[p]++;
}
for (int i=2;i<=tn;i++)
g[a[i].f].push_back(i);
dfs(1);
printf("%lld",1ll*(len-1)*len*(len+1)/2-sum);
return 0;
}
```
**附** : [[DS记录]P5284 [十二省联考2019]字符串问题](https://www.luogu.com.cn/blog/command-block/ds-ji-lu-p5284-shi-er-xing-lian-kao-2019-zi-fu-chuan-wen-ti) (后缀树优化建边)
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
------
# 7.广义 $\rm SAM$
广义 $\rm SAM$ 定义 : 给出多个串,求一个能够识别这些串所有子串的自动机。
构造方法奇为暴力 :
每次加入一个串前,把`las`设为1。
正确性显然(雾)
补记 : 我naive了,Trie树上正牌的广义SAM一点都不会,枯了……
**例题** : [SP8093 JZPGYZ - Sevenk Love Oimaster](https://www.luogu.org/problem/SP8093)
首先对于所有模板串建立广义 $\rm SAM$ ,求出每个点中有多少类模板串的子串,设为`siz`。
对于匹配串在 $\rm SAM$ 上跳,假如跳到空则输出0,否则输出`siz`。
怎么求呢? 我们对第 $i$ 个模板串后缀对应的点染上第 $i$ 种颜色,然后可以静态子树数颜色。
**附** : [CF427D Match & Catch](https://www.luogu.org/problem/CF427D) (近乎广义 $\rm SAM$ 模板)
还有一个奇怪的题 : [Loj#6071. 「2017 山东一轮集训 Day5」字符串](https://loj.ac/problem/6071)
先考虑单个串怎么做,前面我们讲过了可以$\rm parent$树,或者自动机DAG路径计数。
对于多个子串拼接的情况,我们无法构建类似$\rm parent$的强有力的结构,而DAG路径计数更加简单粗暴,只需要满足自动机的基本性质即可。
我们考虑先对每个串单独建立 $\rm SAM$ ,考虑这个DAG的意义,就是从根开始的路径=字符串的每个子串(不重不漏)。
有考虑另一种能跳跃拼接的字符串数据结构 : 子序列自动机。
其做法就是从每个位置`'c'`的出边向后连接到最近的一个`'c'`。
那么,我们考虑把这个若干个 $\rm SAM·DAG$ 魔改一下。
如果某个点没有`'c'`出边,那么连向后面第一个满足要求的的DAG源点的`'c'`出边。
引用某位大佬的话 :
> 现在我们建出来的DAG就非常牛逼了,如果发现想走某一条转移边而没有办法走的时候,它会自动跳到下一个字符串上去,我们在这张DAG上求一下路径总数就是答案了。
看起来很有出题价值。
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#define mod 1000000007
#define sf scanf
#define pf printf
#define MaxN 1005000
using namespace std;
struct Data
{int f,len,t[26];}a[MaxN<<1];
int tn,las,rt[MaxN],frt;
void add(int c)
{
int np=++tn,p=las;las=np;
a[np].len=a[p].len+1;
for (;p&&!a[p].t[c];p=a[p].f)a[p].t[c]=np;
if (!p)a[np].f=frt;
else {
int v=a[p].t[c];
if (a[v].len==a[p].len+1)a[np].f=v;
else {
int nv=++tn;a[nv]=a[v];
a[nv].len=a[p].len+1;
for (;p&&a[p].t[c]==v;p=a[p].f)a[p].t[c]=nv;
a[v].f=a[np].f=nv;
}
}
}
long long dp[MaxN<<1];
void dfs(int u)
{
if (dp[u])return ;
for (int k=0,v;k<26;k++)
if (v=a[u].t[k]){
dfs(v);
dp[u]+=dp[v];
}
dp[u]=(dp[u]+1)%mod;
}
int n,tp[26];
char str[MaxN];
int main()
{
sf("%d",&n);
for (int i=1,len;i<=n;i++){
sf("%s",str);
rt[i]=frt=las=++tn;
len=strlen(str);
for (int j=0;j<len;j++)
add(str[j]-'a');
}rt[n+1]=tn+1;
for (int i=n;i;i--){
for (int j=rt[i];j<rt[i+1];j++)
for (int k=0;k<26;k++)
if (!a[j].t[k])
a[j].t[k]=tp[k];
for (int k=0;k<26;k++)
tp[k]=a[rt[i]].t[k];
}dfs(1);
pf("%lld",dp[1]);
return 0;
}
```
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
------
# 8.线段树合并维护edp
我们发现 $\rm parent$ 树上,父节点的 $\rm edp$ 恰恰是子节点的 $\rm edp$ 求并,这和树上线段树合并太像了!
我们可以考虑使用线段树合并来维护 $\rm edp$ 集合,来干一些神奇的事。
**例题 :** [CF1037H Security](https://www.luogu.org/problemnew/show/CF1037H)
**题意 :** 给一个文章串$S$,给出若干文本串$T$。
截取 $S$ 的一个字串 $S2=S[l...r]$ ,求 $S2$ 的子串中,严格大于 $T$ 的字典序最小的串,如果没有输出-1。
- 我们先考虑没有截取限制,即 $S2=S$。
那么,有一个显而易见的贪心:
先建立$S$的 $\rm SAM$$,然后让$T$在$S$上面跑匹配,我们假设在$T_p$配不上了。
找一个大于当前$T_p$那个字符的最小字符放在串尾即可。
问题在于可能候选的字符都是小于$T_p$的,那我们只能退而求其次,退回上一位,再看看有那个位置没有大于$T_{p-1}$的。
如果退到源点还是没有方案,那么输出-1。
具体的复杂度是$O(|S|+26*\sum|T|)$,那个$26$远远跑不满。
- 现在考虑截取限制,即 $S2=S[l...r]$。
如果我们知道 $S[l...r]$ 的 $\rm SAM$ ,我们就可以套用上述贪心了,但是每次重构复杂度显然不对。
还是要先建立 $S$ 的 $\rm SAM$ ,我们称包含任意一个 $S[l...r]$ 子串的点为“好点”。
那么我们发现,加入我们把所有的“不好点”以及相关的边删掉,那么我们就得到了 $S[l...r]$ 的 $\rm SAM$ 。
这玩意虽然不保证点数边数为 $O(|S[l...r]|)$ ,但还是能恰好匹配所有子串的! (一个合法的自动机)
我们考虑设计一个函数,能够判定某个点是否为好点,那样的话就可以实现上述贪心操作了。
如何判断呢?我们采用线段树合并来维护每个点的 $\rm edp$ 集合,具体做法就是在$\rm parent$树上由下而上合并线段树,空间受得住。注意合并的时候不能销毁儿子的树。
(当然用普通平衡树启发式合并也是可以的,不过代码长,复杂度还多个$\log$)
我们只要在线段树上区间查询一下 $\rm edp$ 有没有值就好了,区间是 $[l+len-1,r]$ 。这里 $len$ 是目前字符串的长度。
那么复杂度就是$O(|S|logn+26*\sum|T|logn)$,看起来比较险,其实由于数据水是**极**松的。
**Code:**
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define MaxN 200500
using namespace std;
int n,q;
char str[MaxN],st[MaxN];
struct $\rm SAM$ _Node
{int t[26],f,len,edp,rt;}
a[MaxN<<1];
int las,tn;
void add(int c)
{
int p=las,np=++tn;las=np;
a[np].len=a[p].len+1;
for (;p&&!a[p].t[c];p=a[p].f)a[p].t[c]=np;
if (!p)a[np].f=1;//case 1
else {
int v=a[p].t[c];
if (a[v].len==a[p].len+1)a[np].f=v;//case 2
else {
int nv=++tn;a[nv]=a[v];
a[nv].len=a[p].len+1;
for (;p&&a[p].t[c]==v;p=a[p].f)a[p].t[c]=nv;
a[np].f=a[v].f=nv;//case 3
}
}
}
vector<int> g[MaxN<<1];
struct SGT_Node
{int l,r;}b[MaxN*41];
int tot;
int marge(int x,int y)
{
if (!x||!y)return x|y;
int pos=++tot;
b[pos].l=marge(b[x].l,b[y].l);
b[pos].r=marge(b[x].r,b[y].r);
return pos;
}
int to;
void add(int l,int r,int &num)
{
if (!num)num=++tot;
if (l==r)return ;
int mid=(l+r)>>1;
if (to<=mid)add(l,mid,b[num].l);
else add(mid+1,r,b[num].r);
}
int wfl,wfr;
bool query(int l,int r,int num)
{
if (!num)return 0;
if (wfl<=l&&r<=wfr)return 1;
int mid=(l+r)>>1;
if (wfl<=mid&&query(l,mid,b[num].l))return 1;
if (mid<wfr&&query(mid+1,r,b[num].r))return 1;
return 0;
}
bool check(int num,int len)
{
bool ans;
wfl+=len-1;
if (wfl>wfr)ans=0;
else ans=query(1,n,a[num].rt);
wfl-=len-1;
return ans;
}
void dfs(int num)
{
if (a[num].edp){
to=a[num].edp;
add(1,n,a[num].rt);
}
for (int i=0,v;i<g[num].size();i++){
dfs(v=g[num][i]);
a[num].rt=marge(a[num].rt,a[v].rt);
}
}
int sp[MaxN];
int main()
{
scanf("%s%d",str,&q);las=tn=1;
n=strlen(str);
for (int i=0;i<n;i++)add(str[i]-'a');
for (int i=0,p=1;i<n;i++){
p=a[p].t[str[i]-'a'];
a[p].edp=i+1;
}for (int i=2;i<=tn;i++)
g[a[i].f].push_back(i);
dfs(1);
for (int qt=1,p,sav,len;qt<=q;qt++){
scanf("%d%d%s",&wfl,&wfr,st);
len=strlen(st);sp[sav=0]=p=1;
for (int i=0;i<len;i++)st[i]-='a';
for (int i=0,v;i<len;i++){
v=a[p].t[st[i]];
if (v&&check(v,i))sp[sav=i+1]=p=v;
else break;
}
st[len]=-1;
char las=100;
for (;las==100&&sav>=0;sav--){
p=sp[sav];
for (int j=st[sav]+1,v;j<26;j++)
if ((v=a[p].t[j])&&check(v,sav+1))
{las=j;break;}
}
if (las==100)puts("-1");
else {
for (int i=0;i<=sav;i++)putchar(st[i]+'a');
putchar(las+'a');putchar('\n');
}
}return 0;
}
```
- [P4094 [HEOI2016/TJOI2016]字符串](https://www.luogu.com.cn/problem/P4094)
先把原串倒过来,现在问题变成了 $[a,b]$ 的子串在 $[c,d]$ 中匹配的最长后缀。
考虑二分一个 $len$ ,就变成了 $O(\log n)$ 个 $[d-len+1,d]$ 在 $[a+len-1,b]$ 中的存在性问题。
令 $c'=d+len-1;a'=a+len-1$.
建立 $\rm SAM$ ,跑一个线段树合并求出每个点的 $\rm edp$。
然后定位包含子串 $[c',d]$ 的那个点,具体方法 : 先找出前缀 $d$ 的对应结束点,然后看 `len` 在$\rm parent$树上倍增。
定位到之后,在当前点看一看有没有 $\rm edp$ 在给出的 $[a',b]$ 内,线段树上一个区间查询就好了。
复杂度 $O(nlog^2n)$ ,常数较大。
[评测记录](https://www.luogu.com.cn/record/28875589)
- [SP687 REPEATS - Repeats](https://www.luogu.com.cn/problem/SP687)
结论 ： 若 $edp$ 中两两元素最小的差为 $g$，那么对答案的贡献即为 $\left\lfloor\dfrac{len-g}{g}\right\rfloor$。
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
------
# 9.SAM上树分治
当你要统计前缀**对子**之间的贡献时,你会发现往往与 $lcs$(最长公共后缀) 有关。
而这又能转化成关于$\rm parent$树上`LCA`的一些信息,那么我们就可以使用有根树分治来统计。
某些时候也可以直接树剖。
- [[DS记录]Loj#6198. 谢特](https://www.luogu.com.cn/blog/command-block/ds-ji-lu-6198-xie-te) (启发式合并01Trie)
- [[DS记录]P5161 WD与数列](https://www.luogu.com.cn/blog/command-block/ds-ji-lu-p5161-wd-yu-shuo-lie) (启发式合并线段树)
- [[DS记录]P4482 [BJWC2018]Border 的四种求法](https://www.luogu.com.cn/blog/command-block/ds-ji-lu-p4482-bjwc2018border-di-si-zhong-qiu-fa) (重链剖分)
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
------
# 10.技巧大杂烩
## 10.1 [P4081 [USACO17DEC]Standing Out from the Herd](https://www.luogu.org/problem/P4081)
设这些串分别为 $S_{1...n}$ ,那么构造出 $S_{[1,i)}$ 的广义 $\rm SAM$ 。
然后,利用 $\rm SAM$ 与AC自动机的相似性,把 $S_{i}$ 在 $S_{[1,i)}$ 的广义 $\rm SAM$ 上匹配一下,然后得到某个前缀在其他串上的匹配长度(取$\max$)。
对于 $S(i,n]$ 的的广义 $\rm SAM$ 也进行同样的匹配操作。
最终可以得到每个串的每个后缀在其他串上的最长匹配长度。
最后对于每个串单独建立 $\rm SAM$ 判重。
具体来讲,就是先随意求出每个点的任意一个 $\rm edp$ ,然后贡献就是根据长度和匹配长度比较,大于匹配长度的那部分才是该串独有的,计入贡献。
[评测记录](https://www.luogu.org/record/22560063)
## 10.2 [P4770 [NOI2018]你的名字](https://www.luogu.org/problem/P4770)
题意: 给出一个文本串和若干询问串,求该询问串没有在文本串**某个区间**中匹配的本质不同子串个数。
首先弱化一下,不考虑那个区间限制。
做法和上一题差不多,先跑个后缀匹配,然后再对询问串建立 $\rm SAM$ 判重就好了。
问题在于现在加上了区间限制,按照套路,先线段树合并弄出 $\rm edp$ 再说。
考虑一下我们匹配的时候究竟在做什么:
- 跑匹配,也就是要知道能不能匹配,以及下一步的出边是什么。
- 读取`len`,这样才知道究竟匹配了多长。
- 发现没有出边,跳$parent$树。
我们要借用原有的 $\rm SAM$ 的框架,来做这三件事情。
在匹配的时候,我们直接取整个 $\rm SAM$ 的出边,然后用线段树查询一下目标节点在要求的区间内有没有 $\rm edp$ ,注意这里**和当前匹配长度也有关**。
注意!失配了之后**不能直接跳`f`**,把匹配的长度减一后,还得再试一次,直到该节点的$len$不对头为止。
怎么读取 $len$ 呢?
考虑到原有 $\rm SAM$ 节点表示的串 : 长度在某个区间内,且 $\rm edp$ 在某某某的所有子串。
现在要求这些子串必须在某个区间内,那么这个长度区间的**上界**就要对某个东西取$\min$,因为最长的串**前面一部分可能被砍掉了**。这会破坏很多(?)性质。
而下界是不会变的,所以比较下界($fa.len$)就知道是否对头了。反正出边会检查,正确性是有保障的。
至于跳`f`这件事,直接在原自动机上跳就好了,可以证明复杂度是正确的(每跳一次匹配长度至少减一),而且不会丢信息。
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define MaxN 1005000
using namespace std;
struct SAM_Node
{int t[26],f,len,edp,rt;};
int wfl,wfr,to;
long long ans=0;
struct SAM
{
char str[MaxN];
SAM_Node a[MaxN<<1];
int las,tn,n;
void add(int c)
{
int p=las,np=++tn;las=np;
a[np].len=a[p].len+1;
for (;p&&!a[p].t[c];p=a[p].f)a[p].t[c]=np;
if (!p)a[np].f=1;//case 1
else {
int v=a[p].t[c];
if (a[v].len==a[p].len+1)a[np].f=v;//case 2
else {
int nv=++tn;a[nv]=a[v];
a[nv].len=a[p].len+1;
for (;p&&a[p].t[c]==v;p=a[p].f)a[p].t[c]=nv;
a[np].f=a[v].f=nv;//case 3
}
}
}
void buildSAM()
{
scanf("%s",str);
n=strlen(str);las=tn=1;
for (int i=0;i<n;i++)add(str[i]-'a');
for (int i=0,p=1;i<n;i++){
p=a[p].t[str[i]-'a'];
a[p].edp=i+1;
}for (int i=1;i<=tn;i++)g[i].clear();
for (int i=2;i<=tn;i++)
g[a[i].f].push_back(i);
}
void dfsedp(int num)
{
for (int i=0,v;i<g[num].size();i++){
dfsedp(v=g[num][i]);
a[num].edp=max(a[num].edp,a[v].edp);
}
}
void build1()
{buildSAM();dfsedp(1);}
struct SGT_Node
{int l,r,x;}b[MaxN*42];
int tot;
int marge(int x,int y)
{
if (!x||!y)return x|y;
int pos=++tot;
b[tot].x=max(b[x].x,b[y].x);
b[pos].l=marge(b[x].l,b[y].l);
b[pos].r=marge(b[x].r,b[y].r);
return pos;
}
void add(int l,int r,int &num)
{
if (!num)num=++tot;
b[num].x=max(b[num].x,to);
if (l==r)return ;
int mid=(l+r)>>1;
if (to<=mid)add(l,mid,b[num].l);
else add(mid+1,r,b[num].r);
}
vector<int> g[MaxN<<1];
void dfs(int num)
{
if (a[num].edp){
to=a[num].edp;
add(1,n,a[num].rt);
}
for (int i=0,v;i<g[num].size();i++){
dfs(v=g[num][i]);
a[num].rt=marge(a[num].rt,a[v].rt);
}
}
void build2()
{buildSAM();tot=0;dfs(1);}
int query(int l,int r,int num)
{
if (!num)return 0;
if (wfl<=l&&r<=wfr)return b[num].x;
int mid=(l+r)>>1,ans=0;
if (mid<wfr)ans=max(ans,query(mid+1,r,b[num].r));
if (!ans&&wfl<=mid)ans=max(ans,query(l,mid,b[num].l));
return ans;
}
bool check(int num,int len)
{
int ans;
wfl+=len-1;
if (wfl>wfr)ans=0;
else ans=query(1,n,a[num].rt);
wfl-=len-1;
return ans>0;
}
void clac(int *slen)
{
ans=0;
for (int i=2;i<=tn;i++)
if (slen[a[i].edp]<a[i].len)
ans+=a[i].len-max(slen[a[i].edp],a[a[i].f].len);
}
void clear()
{
for (int i=1;i<=tn;i++){
for (int j=0;j<26;j++)
a[i].t[j]=0;
a[i].f=a[i].len=a[i].edp=0;
}
}
}S,T;
int q,slen[MaxN];
int main()
{
S.build2();
scanf("%d",&q);
while(q--){
T.build1();
scanf("%d%d",&wfl,&wfr);
int p=1,len=0;
for (int i=0,v;i<T.n;i++){
v=T.str[i]-'a';
while(1){
if (S.check(S.a[p].t[v],len+1))
{p=S.a[p].t[v];len++;break;}
else {
if (p==1){len=0;break;}
len--;
if (len==S.a[S.a[p].f].len)
p=S.a[p].f;
}
}slen[i+1]=len;
}
T.clac(slen);
printf("%lld\n",ans);
T.clear();
}return 0;
}
```
- [题解 CF1098F 【Ж-function】](https://www.luogu.com.cn/blog/command-block/solution-cf1098f)