思想：通过维护子串表示法中\(Right\)与\(len\)来构建\(Parent\)树和\(DAG\)图以表示原字符串所有子串
性质：
①每个节点都代表了一些\(Right\)集合相等的子串，并且记录了长度区间作为辅助信息。
②\(Right\)集合之间是包含关系，包含关系使得这些节点构成了一棵树。称这棵树为\(Parent\)树。
③任取一个非根节点\(x\)，则有\(len_{max}[fa[x]]+1=len_{min}[x]\)。
④向上爬，实际上是尽可能少地缩短字符串前端的长度，以扩大\(Right\)集合的过程。向下转移，实际上是在字符串后端添加一个字符，并且从\(Right\)集合中选出能够接上这个字符的元素。
一个实例：
解说：
图中
实边表示\(Parent\)树上树边(\(Right\)集合包含关系)
红边表示\(a\)，蓝边表示\(b\)(绿边表示\(c\))
从一个表格来看这个\(SAM\)的性质
原串:\(ababaab\)
| \(1\) | (空) | \(1,2,3,4,5,6,7\) | \([0,0]\) |
| \(2\) | \(a\) | \(1,3,5,6\) | \([1,1]\) |
| \(3\) | \(b\),\(ab\) | \(2,4,7\) | \([1,2]\) |
| \(4\) | \(ba\),\(aba\) | \(3,5\) | \([2,3]\) |
| \(5\) | \(bab\),\(abab\) | \(4\) | \([3,4]\) |
| \(6\) | \(baba\),\(ababa\) | \(5\) | \([4,5]\) |
| \(7\) | \(aa\),\(baa\),\(abaa\),\(babaa\),\(ababaa\) | \(6\) | \([2,6]\) |
| \(8\) | \(ababaab\) | \(7\) | \([7,7]\) |
实现：我们考虑在原串基础上加入一个字符
用一个例子来说明
现在我们有了\(S="ababaab"\)的后缀自动机，我们要在\(S\)的后端加上一个新的字符\(x='?'\)(暂定)。8号节点包含了\("ababaab"\)这个串，记录为\(last\)节点。
那么如何得到新的后缀自动机呢？
我们只需要考虑新加入的字符对原后缀自动机造成的影响，并加以调整即可。
①因为\("ababaab?"\)是无法用原有的后缀自动机的节点来表示的，所以我们需要新建节点。该节点包含了\("ababaab?"\)这个串。
②\(last\)不断往上爬，直至到达根节点或者到达某个节点p，p可以读入‘?’这个字符\((ch[p]['?']!=0)\)。
可见
模板
inline void SAM(re int w){
re int x=last,pos=++cnt,y,tmp,i;maxl[pos]=maxl[x]+1;
while(x&&!son[x][w]){son[x][w]=pos;x=fa[x];}
if(!x)fa[pos]=rt;
else{
y=son[x][w];
if(maxl[y]==maxl[x]+1)fa[pos]=y;
else{
tmp=++cnt;maxl[tmp]=maxl[x]+1;
for(i=0;i<26;++i)son[tmp][i]=son[y][i];
fa[tmp]=fa[y];fa[y]=tmp;fa[pos]=tmp;
while(x&&son[x][w]==y){son[x][w]=tmp;x=fa[x];}
}
}
last=pos;
}构造可以看这里
例题部分
思想搞懂了，我们来看看套路题
【一.完全模板】
题意：求两个串最长公共子串
思路:
1.我们把一个串投进SAM
2.对一个串开始逐位比较，分类：
<1>往右延伸一位可以匹配,则累加当前答案
<2>不可匹配就尝试退左边以扩展Right集合，爬Parent树更新当前答案
<3>更新最后答案
inline int Match(re char *str){
re int i,res=0,tlen=0,x=rt,w,len=strlen(str+1);
for(i=1;i<=len;++i){
w=str[i]-'a';
if(son[x][w]){++tlen;x=son[x][w];}
else{
while(x&&!son[x][w])x=fa[x];
if(!x){x=rt;tlen=0;}
else{tlen=maxl[x]+1;x=son[x][w];}
}
res=max(tlen,res);
}
return res;
}题意：求多个串最长公共子串
思路：一个简单的思路是两两匹配，但时间不可行，所以我们干脆记录每个节点状态最小值，树形\(dp\)即可
引入一个技巧，我们在后缀自动机\(Parent\)树上\(dp\)时往往可以不建树，依靠其值域小特性按深度(\(max_{len}\))排序后递推
实现:
for(i=1;i<=len;++i)sum[i]=0;
for(i=1;i<=cnt;++i)sum[maxl[i]]++;
for(i=1;i<=len;++i)sum[i]+=sum[i-1];
for(i=1;i<=cnt;++i)SA[sum[maxl[i]]--]=i;原题部分代码：
Match改成了这样
inline void Match(re char *str){
memset(res,0,sizeof res);
re int i,tmp=0,x=rt,w,len=strlen(str+1);
for(i=1;i<=len;++i){
w=str[i]-'a';
if(son[x][w]){++tmp;x=son[x][w];}
else{
while(x&&!son[x][w])x=fa[x];
if(!x){x=rt;tmp=0;}
else{tmp=maxl[x]+1;x=son[x][w];}
}
res[x]=max(tmp,res[x]);
}
for(i=cnt;i>=1;--i)if(res[SA[i]])res[fa[SA[i]]]=maxl[fa[SA[i]]];
for(i=cnt;i>=1;--i)minn[i]=min(minn[i],res[i]);
}其中
for(i=1;i<=cnt;++i)ans=max(ans,minn[i]);【二.利用性质】
前置性质
1.需要该子串出现次数->\(Right\)集大小(\(Parent\)树上)
想要得到关于每个节点\(Right\)集合的信息，只需要在建立自动机以后按照拓扑序从后往前，用每个节点来更新它的\(fa\)节点就可以了。
for(i=1;i<=len;++i)sum[i]=0;
for(i=1;i<=cnt;++i)sum[maxl[i]]++;
for(i=1;i<=len;++i)sum[i]+=sum[i-1];
for(i=1;i<=cnt;++i)SA[sum[maxl[i]]--]=i;
now=1;for(i=1;i<=len;++i){now=son[now][str[i]-'a'];right[now]=1;}
for(i=cnt;i>=1;--i){
now=SA[i];
right[fa[now]]+=right[now];
}注意到
now=1;for(i=1;i<=len;++i){now=son[now][str[i]-'a'];right[now]=1;}这一句可以改成在SAM函数中\(right[pos]=1\)
2.每个节点往后可以到多少个节点(\(DAG\)中)
for(i=1;i<=len;++i)sum[i]=0;
for(i=1;i<=cnt;++i)sum[maxl[i]]++;
for(i=1;i<=len;++i)sum[i]+=sum[i-1];
for(i=1;i<=cnt;++i)SA[sum[maxl[i]]--]=i;
for(i=cnt;i>=1;--i){
out[SA[i]]=1;
for(j=0;j<26;++j)out[SA[i]]+=out[son[SA[i]][j]];
}思路：
对于这道题目来说，它要求每个长度的串出现次数的最大值，那么只需要对于每个节点递推出它的\(Right\)集合大小，然后映射到长度上面去就可以了。需要注意的一个问题就是如果长度为\(i\)的串出现了\(k\)次，那么长度为\(i-1\)
的串一定至少出现了\(k\)次，因为可以取那些串的后缀。所以最后还要用\(dp(i)\)去更新一下\(dp(i-1)\)。
for(i=1;i<=len;++i)sum[i]=0;
for(i=1;i<=cnt;++i)sum[maxl[i]]++;
for(i=1;i<=len;++i)sum[i]+=sum[i-1];
for(i=1;i<=cnt;++i)SA[sum[maxl[i]]--]=i;
now=1;for(i=1;i<=len;++i){now=son[now][str[i]-'a'];right[now]=1;}
for(i=cnt;i>=1;--i){
now=SA[i];
right[fa[now]]+=right[now];
dp[maxl[now]]=max(dp[maxl[now]],right[now]);
}
for(i=len;i>=1;--i)dp[i]=max(dp[i+1],dp[i]);
for(i=1;i<=len;++i)printf("%d\n",dp[i]);题意：多次询问求字符串第k小子串（本质相同子串不同位置算一个）
在性质2上迭代输出即可
inline void DP_Init(void){
re int i,j;
for(i=1;i<=len;++i)sum[i]=0;
for(i=1;i<=cnt;++i)sum[maxl[i]]++;
for(i=1;i<=len;++i)sum[i]+=sum[i-1];
for(i=1;i<=cnt;++i)SA[sum[maxl[i]]--]=i;
for(i=cnt;i>=1;--i){
dp[SA[i]]=1;
for(j=0;j<26;++j)dp[SA[i]]+=dp[son[SA[i]][j]];
}
}
inline void query(void){
re int i,x=1,y,k;
scanf("%d",&k);
while(k){
for(i=0;i<26;++i){
y=son[x][i];
if(dp[y]>=k){
putchar('a'+i);
x=son[x][i];
--k;break;
}
else k-=dp[y];
}
}
putchar('\n');
}题意：询问求字符串第k小子串（指令1：本质相同子串不同位置算一个 指令2：本质相同子串不同位置算多个）
对指令2把每个节点大小当成其right集大小既可以了
inline void Print(re int x,re int k){
re int i,y;
if(k<=right[x]) return;
k-=right[x];
for(i=0;i<26;++i)
{
y=son[x][i]; if(!y) continue;
if(k>out[y]) {k-=out[y];continue;}
putchar(i+'a');Print(y,k);return;
}
putchar('\n');
}
int main(void){
re int i,len,j;
cnt=rt=last=1;
scanf("%s%d%d",str+1,&opt,&k);len=strlen(str+1);
for(i=1;i<=len;++i)SAM(str[i]-'a');
for(i=1;i<=len;++i)sum[i]=0;
for(i=1;i<=cnt;++i)sum[maxl[i]]++;
for(i=1;i<=len;++i)sum[i]+=sum[i-1];
for(i=1;i<=cnt;++i)SA[sum[maxl[i]]--]=i;
for(i=cnt;i>=1;--i)right[fa[SA[i]]]+=right[SA[i]];
for(i=1;i<=cnt;++i) (opt==1)?(out[i]=right[i]):(out[i]=right[i]=1);
right[1]=out[1]=0;
for(i=cnt;i>=1;--i)
for(j=0;j<26;++j)out[SA[i]]+=out[son[SA[i]][j]];
if(out[1]<k)return fwrite("-1\n",1,4,stdout),0;
Print(1,k);
return 0;
}【三.综合性】
简述：\(LCT+SAM\)
思路:我们考虑所谓的出现次数就是这个字符串在\(SAM\)上跑完对应的\(Right\)集合。要支持及时插入，也就是要动态的维护\(Parent\)树的形态。
因此我们想到了\(link-cut-tree\)
回顾\(Parent tree\)的性质, 一个父亲节点所表示的所有子串的出现位置相同
并且为其所有子节点的子串的出现位置的集合的并。
这个性质就是解决这道题的关键。
所以我们可以用\(link-cut-tree\)维护这一棵\(Parent\)树。（因为要支持加边，同时必须在线）
在插入一个字符时, 对其所对应的\(Parent\)树上到根的路径上的节点全部加\(1\)(后文\(Solve\)函数). 查询时直接输出一个点上的值即可。
实现:
真的困难！！！
看看\(LCT\)的实现
inline void Add(re int x,re int v){if(x){dlt[x]+=v;size[x]+=v;}}
inline void pushdown(re int x){
re int ls=*lctson[x],rs=lctson[x][1];
if(rev[x]){rev[x]=0;swap(*lctson[x],lctson[x][1]);rev[ls]^=1;rev[rs]^=1;}
if(dlt[x]){Add(ls,dlt[x]);Add(rs,dlt[x]);dlt[x]=0;}
}
inline void rot(re int x){
re int y=lctfa[x],z=lctfa[y],l=(*lctson[y]!=x),r=(l^1);
if(Real[y])(*lctson[z]==y)?*lctson[z]=x:lctson[z][1]=x;
else{Real[y]=1;Real[x]=0;}
lctfa[x]=z;lctfa[y]=x;lctfa[lctson[x][r]]=y;
lctson[y][l]=lctson[x][r];lctson[x][r]=y;
}
inline void Splay(re int x){
re int y,z;
pushdown(x);
while(Real[x]){
y=lctfa[x],z=lctfa[y];
if(Real[y])pushdown(z);
pushdown(y);pushdown(x);
if(Real[y])((*lctson[y]==x)^(*lctson[z]==y))?rot(x):rot(y);
rot(x);
}
}
//*杜绝这样的实现
//inline void Access(re int x){
// re int y=0;
// while(Real[x]){
// Real[y]=1;
// Real[lctson[x][1]]=0;
// lctfa[y]=x;
// lctson[x][1]=y;
// y=x;x=lctfa[x];
// }
//}
inline void Access(re int x){
re int y=0;
while(x){
Splay(x);Real[y]=1;
Real[lctson[x][1]]=0;lctson[x][1]=y;
y=x;x=lctfa[x];
}
}
inline void Evert(re int x){Access(x);Splay(x);rev[x]^=1;}
inline void Link(re int x,re int y){Evert(x);lctfa[x]=y;}
inline void Cut(re int x,re int y){Evert(x);Access(y);Splay(y);Real[*lctson[y]]=lctfa[*lctson[y]]=0;*lctson[y]=0;}\(SAM\)实现是这样的
inline void SAM(re int w){
re int i,x=last,y,pos=++cnt,tmp;maxl[pos]=maxl[x]+1;//size[pos]=1; //!!!!!
while(x&&!son[x][w]){son[x][w]=pos;x=fa[x];}
if(!x){fa[pos]=rt;Link(pos,rt);}
else{
y=son[x][w];
if(maxl[y]==maxl[x]+1){fa[pos]=y;Link(pos,y);}
else{
tmp=++cnt;maxl[tmp]=maxl[x]+1;
Splay(y);size[tmp]=size[y];
for(i=0;i<26;++i)son[tmp][i]=son[y][i];
Cut(y,fa[y]);
Link(tmp,fa[y]);Link(y,tmp);Link(pos,tmp);fa[tmp]=fa[y];fa[y]=tmp;fa[pos]=tmp;
while(x&&son[x][w]==y){son[x][w]=tmp;x=fa[x];}
}
}
last=pos;Solve(pos);
}分部分来说说填过(掉过)的坑
一.空间开小
#define N 1200000 //1000000二.此处\(size\)初值不应赋值
re int i,x=last,y,pos=++cnt,tmp;maxl[pos]=maxl[x]+1;//size[pos]=1;三.\(SAM\)中\(tmp\)继承\(pos\)时\(size\)勿漏赋
size[tmp]=size[y];//!!!!!\(query\)和\(main\)就自然而然了
inline int query(re int len){
re int i,x=rt;
for(i=0;i<len;++i)x=son[x][str[i]-'A'];
if(x){Splay(x);return size[x];}
else return 0;
}
int main(void){
re int i,len,ans;
re char opt[N+5];
cnt=last=rt=1;
scanf("%d%s",&q,str+1);len=strlen(str+1);
for(i=1;i<=len;++i)SAM(str[i]-'A');
while(q--){
scanf("%s %s",opt,str);
Decode();len=strlen(str);
if(*opt=='Q'){printf("%d\n",ans=query(len));mask^=ans;}
else{for(i=0;i<len;++i)SAM(str[i]-'A');}
}
return 0;
}思路:虚树+SAM