【学习笔记】字符串—广义后缀自动机
一:【前言】
最近一周都在研究 惊(Ren)艳(Lei)无(Zhi)比(Hui)、美(Li)妙(Xing)绝(Yu)伦(Yue) 的自动机,这里引用 \(\text{bztMinamoto}\) 巨佬的一句话来表达此时的心情:
我感觉我整个人都自动机了…… ——\(bztMinamoto\)(回文自动机学习笔记)
在此过程中发现网上讲广义 \(\text{SAM}\) 的文章很少,而且很多都不正确,所以决定整理一下。
二:【引理】
众所周知,\(\text{SAM}\) 的一个经典应用是求一个字符串中本质不同子串数量,那么如果改为求一个 \(Trie\) 树呢?
刘研绎在 \(2015\) 的国家队论文中说过这样一句话:
大部分可以用后缀自动机处理的字符串的问题均可扩展到 \(Trie\) 树上。
我们将这种建立在 \(Trie\) 树上的 \(\text{SAM}\) 成为广义 \(\text{SAM}\) 。在学习之前,首先要确保对单串 \(\text{SAM}\) 足够熟悉,
其实也可以简单理解为多串 \(\text{SAM}\) 啦QAQ
三:【算法实现】
在用广义 \(\text{SAM}\) 处理多模式串问题时,网上流传着的主流写法有 \(3\) 种:
\((1).\) 用特殊符号将所有模式串连成一个大串放到一个 \(\text{SAM}\) 中,用一些玄学特判来处理。
\((2).\) 每次插入一个模式串之前,都把 \(last\) 设为 \(1\),按照普通 \(\text{SAM}\) 一样插入,即每个字符串都从起点 \(1\) 开始重新构造。
\((3).\) 用所有模式串建出一颗 \(Trie\) 树,对其进行 \(bfs\) 遍历构建 \(\text{SAM}\),\(insert\) 时 使 \(last\) 为它在 \(Trie\) 树上的父亲,其余和普通 \(\text{SAM}\) 一样。
第一种实用性不高且复杂度危险,第二种听机房大佬说是盗版,但因为很少出问题且代码简单,所以很多人都用的这种。但根据广义 \(\text{SAM}\) 的定义,只有第三种才是标准写法。
这里有一个疑问:为什么是 \(bfs\) 而不用 \(dfs\) 呢?在某些特定情况下,\(dfs\) 会被卡成 \(O(n^2)\) 而 \(bfs\) 不会,具体见 这里(翻遍全网找到的唯一一篇细讲广义 \(\text{SAM}\) 准确写法的博客)。
\(bfs\) 代码如下:
//Trie.tr[x]: Trie树的状态转移数组
//Trie.fa[x]: Trie树上节点x的父节点
//Trie.c[x]: Trie树上节点x的字符
//pos[x]:Trie上x节点的前缀字符串(路径 根->x 所表示的字符串)在SAM上的对应节点编号
inline void build(){//bfs遍历Trie树构造广义SAM
for(Re i=0;i<C;++i)if(Trie.tr[1][i])Q.push(Trie.tr[1][i]);//插入第一层字符
pos[1]=1;//Tire树上的根1在SAM上的位置为根1
while(!Q.empty()){
Re x=Q.front();Q.pop();
pos[x]=insert(Trie.c[x],pos[Trie.fa[x]]);//注意是pos[Trie->fa[x]]
for(Re i=0;i<C;++i)if(Trie.tr[x][i])Q.push(Trie.tr[x][i]);
}
}
而实际上建立起 \(Trie\) 树后再构造 \(\text{SAM}\) 是一种离线写法,我们也可以不建 \(Trie\) 树直接在线构造:
每次插入一个模式串之前,都把 \(last\) 设为 \(1\),\(insert\) 函数在普通 \(\text{SAM}\) 的基础上加入特判(注意前面说的盗版写法用的是不加特判的普通 \(insert\))。
更改后的 \(insert\) 代码如下:
//link[i]: 后缀链接
//trans[i]: 状态转移数组
inline int insert(Re ch,Re last){//将ch[now]接到last后面
if(trans[last][ch]&&maxlen[last]+1==maxlen[trans[last][ch]])return trans[last][ch];
//已经存在需要的节点(特判1)
Re x,y,z=++O,p=last,flag=0;maxlen[z]=maxlen[last]+1;
while(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];
if(!p)link[z]=1;
else{
x=trans[p][ch];
if(maxlen[p]+1==maxlen[x])link[z]=x;
else{//需要拆分x,将len<=maxlen[p]+1的部分复制一个y出来
if(maxlen[p]+1==maxlen[z]/*或者写:p==last*/)flag=1;(特判2)
y=++O;maxlen[y]=maxlen[p]+1;
for(Re i=0;i<C;++i)trans[y][i]=trans[x][i];
while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
link[y]=link[x],link[z]=link[x]=y;
}
}
return flag?y:z;
//返回值为:ch[now]插入到SAM中的节点编号,
//如果now不是某个字符串的最后一个字符,
//那么这次返回值将作为下一次插入时的last
}
加入返回值是方便记录 \(last\)。
接下来我们重点研究一下这两个特判的具体含义:
(特判1)
if(trans[last][ch]&&maxlen[last]+1==maxlen[trans[last][ch]])
return trans[last][ch];
(特判2)
if(maxlen[p]+1==maxlen[z]/*或者写:p==last*/)flag=1;
特判 \(1\) 比较好理解,我们想要在 \(last\) 后面插入一个节点 \(z\) 使得 \(maxlen[z]=maxlen[last]+1\),而这个节点已经存在于\(\text{SAM}\) 中了,那么就可以直接返回。
注意:这里返回的这个节点保存了多个模式串的状态,即将多个不同模式串的相同子串信息压缩在了这一个节点内,如果要记录 \(endpos\) 大小的话,需要给每个模式串都单独开一个 \(siz\) 数组依次更新,而不能全部揉成一坨。【例】
特判 \(2\) 的实质是处理 \(trans[last][ch]\ !\!=NULL\) 且 \(maxlen[last]+1\ !\!=maxlen[trans[last][ch]]\) 的情况。
我们先来看看单串 \(\text{SAM}\) 的 \(insert\) 图示(来源于 \(\text{hihocoder}\)):
在从 \(last\) 开始往前跳 \(link\) 时,单串 \(\text{SAM}\) 中必定存在着 \(trans[p][ch]=NULL\) 的一段,但扩展到多串后可能就没有这一段了,即存在 \(trans[last][ch]=x\),可知 \(maxlen[p]+1\ !\!=maxlen[x]\)(如果相同的话,在特判 \(1\) 时就返回了鸭),如下图:
显然,此时没有任何节点指向最初新建的 \(z\) 节点,同时它没有记录任何信息,新加入的信息全部储存在了 \(link[z]=y\) 节点上面(即 \(x\) 拆分出来的复制点),但通常情况下它作为一个空节点不会对答案造成任何影响(为什么是空的呢?其后缀链接会指向 \(trans[last][ch]\) 的复制节点 \(y\),而 \(maxlen[y]=maxlen[last]+1\),所以 \(minlen[z]=maxlen[link[z]=y]+1=maxlen[last]+2\),又有 \(maxlen[z]=maxlen[last]+1\),所以 \(z\) 为空 )。
从另一个角度看,节点 \(y\) 满足 \(trans[last][ch]=y\) 且 \(maxlen[y]=maxlen[last]+1\),这不正是我们想要的吗(同特判 \(1\)),所以可以返回 \(y\)。
其实通常情况下,不加特判 \(2\) 也不会出啥事,无非就是多跳了一次 \(link\),但在统计某些特定的信息时可能会挂 【例】,所以还是建议推荐加上这一句。
疑问:在线和离线有什么不同呢?
在特判 \(1\) 的作用下,在线写法会构造出一颗类 \(Trie\) 形态的 \(\text{SAM}\),其本质还是在一颗没有具象化的 \(Trie\) 树上建立了 \(\text{SAM}\)。
四:【广义SAM的复杂度】
设 \(|T|\) 为 \(Trie\) 树大小,\(|A|\) 为字符集大小(可视为常数),\(G(T)\) 为 \(Trie\) 树所有叶节点深度之和。
状态数(节点数)依旧为线性 \(O(2|T|)\) 。
转移函数(边数)上界为 \(O(|T||A|)\) 。
离线时间复杂度为 \(O(|T||A|+|T|)\) 。
在线时间复杂度为 \(O(|T||A|+G(T))\) 。
上述性质在 \(2015\) 年刘研绎的国家队论文都中有严谨证明,这里不赘述。
五:【例题】
传送门:诸神眷顾的幻想乡 \(\text{[ZJOI2015] [P3346]}\) \(\text{[Bzoj3926]}\)
给出一颗叶子结点不超过 \(20\) 个节点的无根树,每个节点上都有一个不超过 \(10\) 的数字,求树上本质不同的路径树(两条路径相同定义为 其路径上所有节点上的数字依次相连组成的字符串相同)。
首先有一个很麻烦的地方是路径可以拐弯(即两端点分别在其 \(lca\) 两个不同儿子节点的子树中),而 \(Trie\) 和各种自动机在“接受”字符串时都是以根为起点从上往下径直走到底(什么?跳 \(Parent\) 树?你跳任你跳,跳完还是直的)
所以要想办法把路径捋直,瞎 \(yy\) 可能不太容易想出来,这里直接抛结论:
- 一颗无根树上任意一条路径必定可以在以某个叶节点为根时,变成一条从上到下的路径(利于广义 \(\text{SAM}\) 的使用)。
注意到题目中说叶节点不超过 \(20\) 个,这意味着什么?
暴力枚举每一个叶节点作为根节点遍历整棵树啊!
将一共 \(cnt_{leaf}\) 颗树中的所有前缀串都抽出来建立广义 \(\text{SAM}\),然后就可以求本质不同的子串了。 其中前缀串即是从根节点(无根树的某个叶子结点)到任意一个节点的路径所构成的字符串(实际上就是将 \(cnt_{leaf}\) 颗 \(Trie\) 树合在了一起跑广义 \(\text{SAM}\))。
注意数组大小和空间限制。
【Code】
【离线】
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
#define LL long long
using namespace std;
const int N=4e6+5,N20=2e6+3,Nn=1e5+3;
int n,m,o,x,y,t,C,du[Nn],co[Nn],head[Nn];LL ans;
struct QAQ{int to,next;}a[Nn<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
int fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
struct Trie{
int O,c[N20],fa[N20],tr[N20][10];
//fa[x]: Trie树上x的父节点
//c[x]: Trie树上x的颜色
Trie(){O=1;}//根初始化为1
inline int insert(Re p,Re ch){//在p后面插入一个ch
if(!tr[p][ch])tr[p][ch]=++O,c[O]=ch,fa[O]=p;
return tr[p][ch];
}
}T1;
struct Suffix_Automaton{
int O,pos[N],link[N],trans[N][10],maxlen[N];queue<int>Q;
//pos[x]:Trie上的x节点(路径1->x所表示的字符串)在SAM上的对应节点编号
//link[i]: 后缀链接
//trans[i]: 状态转移数组
Suffix_Automaton(){O=1;}//根初始化为1
inline int insert(Re ch,Re last){//和普通SAM一模一样
Re x,y,z=++O,p=last;maxlen[z]=maxlen[last]+1;
while(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];
if(!p)link[z]=1;
else{
x=trans[p][ch];
if(maxlen[p]+1==maxlen[x])link[z]=x;
else{
y=++O;maxlen[y]=maxlen[p]+1;
for(Re i=0;i<C;++i)trans[y][i]=trans[x][i];
while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
link[y]=link[x],link[z]=link[x]=y;
}
}
return z;
}
inline void build(){//bfs遍历Trie树构造广义SAM
for(Re i=0;i<C;++i)if(T1.tr[1][i])Q.push(T1.tr[1][i]);//插入第一层字符
pos[1]=1;//Tire树上的根1在SAM上的位置为根1
while(!Q.empty()){
Re x=Q.front();Q.pop();
pos[x]=insert(T1.c[x],pos[T1.fa[x]]);//注意是pos[Trie->fa[x]]
for(Re i=0;i<C;++i)if(T1.tr[x][i])Q.push(T1.tr[x][i]);
}
}
inline void sakura(){
for(Re i=2;i<=O;++i)ans+=maxlen[i]-maxlen[link[i]];
printf("%lld\n",ans);
}
}SAM;
inline void dfs(Re x,Re fa,Re fap){//便利构造Trie树
Re xp=T1.insert(fap,co[x]);//记录在Trie树上的位置,方便下次直接使用
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa)dfs(to,x,xp);
}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(C),m=n-1;
for(Re i=1;i<=n;++i)in(co[i]);
while(m--)in(x),in(y),add(x,y),add(y,x),++du[x],++du[y];
for(Re i=1;i<=n;++i)if(du[i]==1)dfs(i,0,1);//以此把每个叶子节点作为根插入Trie树
SAM.build(),SAM.sakura();
}
【在线】
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
#define LL long long
using namespace std;
const int N=4e6+5,N20=2e6+3,Nn=1e5+3;
int n,m,o,x,y,t,C,du[Nn],co[Nn],head[Nn];LL ans;
struct QAQ{int to,next;}a[Nn<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
int fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
struct Suffix_Automaton{
int O,link[N],trans[N][10],maxlen[N];
//link[i]: 后缀链接
//trans[i]: 状态转移数组
Suffix_Automaton(){O=1;}//根初始化为1
inline int insert(Re ch,Re last){
if(trans[last][ch]&&maxlen[last]+1==maxlen[trans[last][ch]])return trans[last][ch];//已经存在需要的节点
Re x,y,z=++O,p=last,flag=0;maxlen[z]=maxlen[last]+1;
while(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];
if(!p)link[z]=1;
else{
x=trans[p][ch];
if(maxlen[p]+1==maxlen[x])link[z]=x;
else{
if(maxlen[p]+1==maxlen[z]/*或者写:p==last*/)flag=1;
y=++O;maxlen[y]=maxlen[p]+1;
for(Re i=0;i<C;++i)trans[y][i]=trans[x][i];
while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
link[y]=link[x],link[z]=link[x]=y;
}
}
return flag?y:z;
}
inline void sakura(){
for(Re i=2;i<=O;++i)ans+=maxlen[i]-maxlen[link[i]];
printf("%lld\n",ans);
}
}SAM;
inline void dfs(Re x,Re fa,Re fap){//遍历在线构造SAM
Re xp=SAM.insert(co[x],fap);//记录x在SAM上的位置,方便下次直接使用
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa)dfs(to,x,xp);
}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(C),m=n-1;
for(Re i=1;i<=n;++i)in(co[i]);
while(m--)in(x),in(y),add(x,y),add(y,x),++du[x],++du[y];
for(Re i=1;i<=n;++i)if(du[i]==1)dfs(i,0,1);//以此把每个叶子节点作为根插入Trie树
SAM.sakura();
}