广义SAM用来处理多个字符串的子串的问题。一般是先建trie,再在trie上建SAM。也可以不建trie直接每次插一个串,每次需要把lst设为S。
复杂度是O(trie树节点数)的。所以一般复杂度和加特殊字符拼接好像没什么区别。
不过如果trie树是题目给你的那就可以放心用了。

在trie上建SAM的方法是插入p节点时先把lst置为父亲所在状态,好像挺简单的。若插入字符时当前节点已有这个出边,要像q一样判一下mxlen,具体看代码。

例题:[ZJOI2015]诸神眷顾的幻想乡

给你一棵字符构成的树,保证叶子节点不超过20个,问树上所有简单路径构成不同的字符串有多少。

这个就是广义SAM的裸题了。考虑叶子节点少,于是我们可以分别把这些叶子当根建SAM即可。

对于在trie上建SAM还有一个小问题,就是遍历trie的方式。有bfs和dfs两种,那么选哪种呢?事实上,dfs是可以被卡成O(n2)O(n^2)的。

数据生成器:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int n=N-1,m=N>>1;
int main(){
    printf("%d\n",n);
    for(int i=1;i<=m;i++)printf("0 ");
    for(int i=m+1;i<=n;i++)printf("1 ");
    puts("");
    for(int i=m+1;i<=n;i++)printf("%d %d\n",n-i+1,i);
    for(int i=2;i<=m;i++)printf("%d %d\n",i-1,i);
    return 0;
}

但是对于这道题目,dfs的遍历方式是可以A掉的,叶子数的限制使得他无法构造这样的数据。
贴上bfs的代码:

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=2e6+50;
int n,c,a[N],ver[N],nxt[N],head[N],tot,d[N],p[N],link[N],trans[N][10],mxlen[N],cnt=1,lst=1,q[N],l,r,f[N];LL ans;
int read(){
	int x=0,c;
	while(!isdigit(c=getchar()));
	while(isdigit(c))x=x*10+(c^48),c=getchar();
	return x;
}
void add(int x,int y){ver[++tot]=y;nxt[tot]=head[x];head[x]=tot;d[y]++;}
void extend(int c){
	int cur=0,p=lst;
	if(!trans[p][c])lst=cur=++cnt,mxlen[cur]=mxlen[p]+1;
	for(;p&&!trans[p][c];p=link[p])trans[p][c]=cur;
	if(!p)link[cur]=1;
	else{
		int q=trans[p][c];
		if(mxlen[q]==mxlen[p]+1){cur?link[cur]=q:lst=q;}
		else{
			int nq=++cnt;cur?0:lst=nq;
			memcpy(trans[nq],trans[q],sizeof(trans[q]));
			mxlen[nq]=mxlen[p]+1;link[nq]=link[q];
			for(;p&&trans[p][c]==q;p=link[p])trans[p][c]=nq;
			link[q]=nq;if(cur)link[cur]=nq;
		}
	}
}
void bfs(int x){
    q[l=r=1]=x;f[x]=0;
    while(l<=r){
        int x=q[l++];
        lst=p[f[x]];extend(a[x]);p[x]=lst;
        for(int i=head[x],y;i;i=nxt[i])if((y=ver[i])^f[x])f[y]=x,q[++r]=y;
    }
}
int main(){
	scanf("%d%d",&n,&c);p[0]=1;
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1,x,y;i<n;i++)x=read(),y=read(),add(x,y),add(y,x);
	for(int i=1;i<=n;i++)if(d[i]==1)bfs(i);
	for(int i=2;i<=cnt;i++)ans+=mxlen[i]-mxlen[link[i]];
	printf("%lld\n",ans);
	return 0;
}

完结撒花!
下面还有一些要记录的性质:

  • 一个串的所有子串在广义后缀自动机中所在的状态量仍然是O(len)级别的(ztb说可以卡,hack咕咕咕),可以通过打标记暴力跳父亲的方式不重不漏地访问到。看一眼代码:
for(int i=1;i<=n;i++)for(int j=1,p=1;j<=len[i];j++){
    p=trans[p][s[i][j]-'a'];
    for(int l=p;l;l=par[l])
        if(flag[l]^i)flag[l]=i,v[i].push_back(l);
        else break;
}

我们来hack它233,想要hack的话就是让状态量达到O(len2)O(len^2)级别,那么有一种方法是先造一个主串,输出它所有的子串。于是所有的状态都会裂开,对于每个串的状态量都达到了O(len2)O(len^2)级别。

那么来分析一下复杂度:设主串长度为n,则输入总长达到O(n3)O(n^3)级别,算法复杂度是O(n4)O(n^4)级别。那么关于总长的复杂度就是O(n43)O(n^\frac{4}{3})。还是很优秀嘛,不知道还有没有什么更优秀的hack。咕咕咕

这是我随便rand的一个长度为200的主串的结果,第一个输出是总串长,第二个是访问到的总状态数。应该说的确到达了这个复杂度。
据说这样复杂度是O(nn)O(n\sqrt n)的qwq