[学习笔记] SAM——后缀自动机

零.前言

​ 真是给我整的有够难受的，这个SAM，也不算搞懂了。只是粗浅的理解了一下，且在这里试图将它写下来。

​ 上面是这个笔记的初稿，现在做了一些题，感觉自己不说懂完了，但是还是有一点点点点东西的。/cy

一.概念

1.自动机

​ 感兴趣的可以自主找资料看一下，很有趣的一个概念，能够帮助你理解各路自动机，由于不是重点，所以这里不加以阐释。

2.后缀自动机(Suffix automaton,SAM)

​ 为对应字符串的所有子串的压缩形式，节点数最多为 \(2n-1\),转移边最多有 \(3n-4\) 条。这些性质在后面会给出论证。此处不做讲解

​ 组成部分分有两个，一个是它的自动机部分，为一个有向无环图，图上的每一个点被称为是一个“状态”，每一个边称为“转移”，图上的源点称为初始状态。另外一个是一棵树，多被称为 \(Parent~tree\) ,每一个点也是状态，但是边为 "后缀链接"，初始状态为这棵树的根。此处也暂时不做证明。

​ 接下来给出上面所有加粗术语的内涵。

3.状态

​ 又被称为一个 “\(Endpos\) 等价类”，或者叫 "\(right\) 集合"。

​ 对于子串 s，它的所有出现位置（以 "right" ，即最后一个字母(end) 出现的位置( position )为代表),可以构成一个集合 S。那么集合相同的所有串被同一个状态所代表。

​ 取这些串中的最长的串为 \(s_{max}\) 那么状态上会储存它的长度 \(Len\)。

4.转移

​ 每个转移上有一个字符 c ，那么经过这条转移相当于在串的末尾添加一个字符 c。每一个状态所对应的所有转移互不相同。且这个状态所代表的所有串都可以走这个转移到一个相同的状态中。

5.后缀链接

​ 表示状态 \(endpos\) 包含关系的连边。若是等价类 \(S \subset 等价类A\) 那么从 S 对应的状态向 A 对应的状态连边。

6.论证与清新理解

​ 这里就是我得私货了，是我自己关于以上概念的一些不成熟的想法，跟算法没有什么关系，只是我得一些小想法。不想看可以不看。

trie与 parent tree 与后缀链接 与 状态 和后缀树

​ 首先每一个子串都会有一个与之相对应的状态，虽然并不一一对应。那么作为一个及其特殊的子串——空串，存在于所有位置，他会恰好对应一个最大的集合，也就是初始状态，parent tree 的树根，因为所有的状态上的 endpos 集合都被初始状态的集合所包含。

​ 那么考虑一个向前的“扩展”的过程，对于一个子串\(A\)，我们通过在其前面添加一个字符，变成一个更长的合法子串\(B=cA\)。容易想出，B 对应的集合是包含于A的。一方面可以考虑 A 是 B 的真后缀，所以所有 B 出现的 endpos ，A 也一定出现。另一方面可以认为我们使 B 变得更为特殊，出现条件更为苛刻，所以满足条件的位置更少。

​ 然后将扩展想象成伸出一条带字母的边，可以认为是在不断的向下“生长”成为一颗树。

​ 那么如此想像，可以得到一颗树，很有趣的是，它和将所有子串倒着插成一个 \(trie\) 的结果相同。很可悲的是，他跟SAM中的树还暂时没有什么关系。这颗 tire 上的每一个点到根代表着一个子串，对于每一个子串，也只对应一个点，然后不妨将这个子串在原串中的出现次数标到点上。

​ 若是存在连续一段中间没有分叉且出现次数相同的部分，我们就可以将它压缩成同一个点，实际上是后缀树的定义，这样压缩下来就成为了SAM对应的 parent tree，而其中剩下的边即为后缀链接。且这个时候也能说明为什么 \(endpos\) 等价类之间形成一个树关系。

​ 可能听着觉得很奇怪。但这个想法实际上反映了 \(endpos\) 等价类的许多内涵。记这个段上某一个点为 \(A\) 它的父亲为 \(B\) .没有分叉，证明了所有的子串 B 向前 “扩展” 只能成为 A，同时树的性质也决定了所有的 A 也只由 B 扩展而来。再换句话说，有 A 的地方就有 B ，有 B 的地方就有 A，且 A 为 B 的后缀。这满足了 \(endpos\) 等价类的意义。需要注意的是，当 B 为 'a' ，A 为 'aa' ，不满足意义，因为出现次数不同。

​ 同时原来 tire 中的边就是反映的一个子串间的后缀关系，而后缀链接作为边的一部分同样也可以反映，所以叫 “后缀” 链接，更具体的，记后缀链接 \((p,q)\),所以 q 中的串为 p 中的串的后缀。（由于压缩的意义，一个状态已经包含很多个串了）

​ 所以可以快速证明以下几个引理。

• 字符串 S 的两个非空子串 u 和 w （假设 |u|<=|w| ,可以得到在 tire 中 u 为 w 的祖先）的 相同，当且仅当字符串 u 在 s 中的每次出现，都是以 w 后缀的形式存在的。

  很显然，endpos等价类来源于压缩的过程，而压缩前的tire 保证了后缀关系。

• 同样条件下，\(endpos(u)\) 和 \(endpos(w)\) 不交叉，即交集要么为空要么为 \(endpos(w)\)

  同样很好证，tire树的形态保证了节点要么包含要么不交。

• 考虑一个 \(endpos\) 等价类，将类中的所有子串按长度非递增的顺序排序。每个子串都不会比它前一个子串长，与此同时每个子串也是它前一个子串的后缀。换句话说，对于同一等价类的任一两子串，较短者为较长者的后缀，且该等价类中的子串长度恰好覆盖整个区间 。

  易证，本来在tire上就是后缀关系，合在一起并不破坏关系。

• 对于原串 S 的任一前缀，均为其所在的状态中最长的串。

  易证，由于是前缀，所以在原 trie 中到达叶子节点，能和他合并的并没有比他长的。同时这个在增量构建的方式中也看得出来。

• 所有的前缀在 parent tree 中均为叶子节点，且充要。

  自证不难。不想写了。

状态与转移

​ 与“扩展”在前面加一个字符的形式不同，转移时在后面添加一个字符。于是连边就连向对应的 \(endpos\) 等价类就好。然后这个自动机是一个有向无环图也很好证，因为每走一个转移长度会加1，所以不可能走到他自己，所以无环。

状态数的证明

​ 从之前的理解来看，容易发现叶子节点均为一个前缀，于是可以知道 parent tree 是一个内部节点除了部分特殊点（前文提到的 'aa' 与 'a'，而且这种东西只会在一个前缀均为同一字母的时候才为链，可以思考为什么，或者直接画图检验）都有着不止一个儿子，而叶子节点最多只有前缀个数即 |S| 个（顶不到的情况是特殊点，会消耗叶子节点数，状态数更小），于是 “任意内部节点读书至少为2，叶子节点最多为 n”的树，点数最多为 \(2n-1\)

​ 当然也可以从构造算法看。

转移数的证明

​ 咕咕咕。

二.构造

​ 扯了一堆没什么卵用的。

​ 现在来说SAM的构造，首先这是一个在线的构造，对于每次新增的一个字符 c ，插入一个可以代表他的状态 cur 。要维护他在 parent tree 上的位置以及转移。不妨记上一次插入的状态为 last 。那么很显然的 last 为上一次插入的 cur，且每一次插入的都是代表整个串，即集合{end}.

​ 那么要维护它的转移。

​ 由于转移是相当于在后面加一个合法的字符，所以理论上来讲所有的原后缀都可以增添一个转移到 cur 。由于 last 代表整个原串，所以顺着 last 在 parent tree 上到根的路径就可以遍历出所有的后缀，并且试图在其后添加一个到 cur 的转移。

​ 但是当某一个代表原后缀的状态 p ，拥有一个为 c 的转移的时候，就会产生“冲突”，这和我们概念所保证的每一个状态中转移互不相同不一样。于是尝试去解决这个问题。

​ 开始观察 p 经过 c 转移所到达的状态 q。首先设想一个非常简单的情况，q 中最长的串为 \(xc\) ，那么很幸运地是此时可以直接将 cur 的后缀链接连到 q 上去，因为满足在上面所提到的“后缀链接 \((a,b)\), b 中最长的串为 a 中最短的串的后缀”。当最长的串为 \(dxc\) 的时候，情况变得了复杂起来。因为并不满足性质。

​ 这种情况之所以会出现，是因为之前压缩的太过度了。这种情况下最憨的想法是将那个状态拆回 tire 上的形式，然后在压缩。经过手玩之后，我们发现这个过程产生了一个新的状态，且这个状态恰好代表 \(xc\) ，而它的一个儿子最短的串都比\(xc\) 在前面多一个字符 。此时就可以将 cur 接上去了。并且发现这两个状态的信息十分的相似，唯一的差别就是最长串的长度，信息的相似读者自证奥。

​ 最后一步是处理转移，因为有且只有 p 的后缀都可以走 c 的转移到 q，但是，转移出来的串长度可能是原来的 q 中长度大于 \(xc\) 的那一部分，所以有一个转移分流。

​ 所以给出构造的代码。

CODE

struct node{
	int len,link,siz;//最大串长度，后缀链接，出现次数（后文会讲）
	map<char , int > tran;//转移
}alf[MAXN];
inline void SAM_insert(char c){
	int cur=++tot,now=last;
	alf[cur].len=alf[last].len+1;
	alf[cur].siz=1;
	while(now!=-1&&!alf[now].tran[c])alf[now].tran[c]=cur,now=alf[now].link;//顺着跳，加转移
	if(now==-1)alf[cur].link=0;//它的合法真后缀就只有空串了
	else{
		int bet=alf[now].tran[c];
		if(alf[bet].len==alf[now].len+1)alf[cur].link=bet;//简易情况
		else {
			int clone=++tot;//拆点
			alf[clone]=alf[bet];//复制
			alf[clone].len=alf[now].len+1,alf[clone].siz=0;//更新串长与出现次数
			while(now!=-1&&alf[now].tran[c]==bet)alf[now].tran[c]=clone,now=alf[now].link;//转移分流
			alf[cur].link=alf[bet].link=clone;//链起来
		}
	} 
	last=cur;
}

​ 同时很有趣的是，我们拆出一个新点，恰好给他了两个儿子，并不破环 parent tree 的性质，并且每一次操作只会产生一个新点，所以总状态数是 \(2n\) 级别的。

​ 总共构建的复杂度不会算。

​ 并且由于是增量构建的，所以每插入一个完成后，都可以识别当前所有的后缀，而当前是一个前缀，之后也并不删除信息，故能识别所有前缀的所有后缀，即所有子串。

三.应用选讲

​ 此处总结了一些见过和想到的东西。还是题做少了。

1.本质不同子串数

​ 将所有状态上的 len 和父亲的 len 做差即可。

2.第 k 小子串

​ 可以知道一条转移序列和一个子串一一对应，等于是在DAG上面先DP出每一个状态走任意转移能得到的子串数，然后贪心即可，有点类似于平衡树上第 k 小。

3.某子串在文本串中的出现次数

​ 直接拿文本串 S 大力跑，能转移就转移，不能转移就跳 link 直到能转移。这一步其实很贪心，因为跳 link 相当于在前面删去尽可能少的字符，然后看是否够转移。

​ 同时注意到由于相当于删去，最多跳 |S| 次，最多转移 |S| 次，所以线性。

​ 最后统计答案的时候需要将子树内答案累加，因为后缀链接代表后缀关系，那么一个串出现即代表它的所有后缀都出现。

4.两个字符串最长公共子串

​ 还是拿一个建，另一个大力跑，然后记录一下当前匹配到的长度 \(Len(i)\) 表示在 i 位置匹配到了一个长度为 \(Len(i)\) 的串，取 Len 的最大值即可。

​ 具体的计算，在走转移时 \(Len(i)\) 就+1，跳 link 的时候就置为状态上的 len，感觉不太需要解释，毕竟贪心。

​ 例题

5.多个字符串最长公共子串

​ 方法同上，只是单次要在子树内取最大，全局要取每一次最小。

​ 例题

CODE

#define fe(i,a,b) for(int i=a;i<=b;++i)
const int MAXN=1e5+5;
struct node{
	int trans[30],link,len,ans,nowans;
	vector<int> ch;
	inline void upd(int x){nowans=min(len,max(nowans,x));}
}alf[MAXN*2-1];
int tot,last,ans;
inline void SAM_insert(int c){
	int cur=++tot,now=last;
	alf[cur].len=alf[last].len+1,alf[cur].ans=1e9;
	while(now!=-1&&!alf[now].trans[c])alf[now].trans[c]=cur,now=alf[now].link;
	if(now==-1)alf[cur].link=0;
	else{
		int bet=alf[now].trans[c];
		if(alf[bet].len==alf[now].len+1)alf[cur].link=bet;
		else{
			int clone=++tot;
			alf[clone]=alf[bet],alf[clone].len=alf[now].len+1;
			while(now!=-1&&alf[now].trans[c]==bet)alf[now].trans[c]=clone,now=alf[now].link;
			alf[cur].link=alf[bet].link=clone;
		}
	}
	last=cur;
}
char s[MAXN];
inline void solve(int x){
	int siz=alf[x].ch.size();
	fe(i,0,siz-1)solve(alf[x].ch[i]);
	alf[x].ans=min(alf[x].ans,alf[x].nowans);
	if(x)alf[alf[x].link].upd(alf[x].nowans);
}
int main(){
	scanf("%s",s+1);
	alf[0].link=-1;
	int len=strlen(s+1);
	fe(i,1,len)SAM_insert(s[i]-'a');
	fe(i,1,tot)alf[alf[i].link].ch.push_back(i);
	while(scanf("%s",s+1)!=EOF){
		fe(i,0,tot)alf[i].nowans=0;
		len=strlen(s+1);
		int now=0,cnt=0;
		fe(i,1,len){
			if(alf[now].trans[s[i]-'a'])now=alf[now].trans[s[i]-'a'],cnt++;
			else {
				while(now!=-1&&!alf[now].trans[s[i]-'a'])now=alf[now].link;
				if(now!=-1)cnt=alf[now].len+1,now=alf[now].trans[s[i]-'a'];
				else now=cnt=0;
			}
			alf[now].upd(cnt);
		}
		solve(0);
	}
	fe(i,1,tot)ans=max(ans,alf[i].ans);
	printf("%d",ans);
	return 0;
}

6.一个串和另一个串的某一区间的最长公共子串

例题

​ 这是一个很典型的 \(i-Len(i)\) 的模型，原题对于每一个询问 \([l,r]\)，相当于求 \(\max_{l\leq i\leq r}\{\min\{Len_i,i-l+1\}\}\)。考虑 min 号里面两项做差，抛开常数即为 \(i-Len(i)\),容易发现这个东西单调不降。因为向后走 i 肯定能增大，而 Len 最多增大1.所以有单调性。直接二分看什么时候取那一边就完事了。

CODE

#define fe(i,a,b) for(int i=a;i<=b;++i)
const int MAXN=2e5+5;
struct node{
	int trans[30],link,len;
}alf[MAXN*2-1];
int tot,last;
inline void SAM_insert(int c){
	...
}
char s[MAXN],t[MAXN];
int bet[MAXN],Q,RMQ[MAXN][20],lg2[MAXN],lent,len;
inline int ST_query(int l,int r){
	int k=lg2[r-l+1];
	return max(RMQ[l][k],RMQ[r-(1<<k)+1][k]);
}
inline void ST_init(){
	fe(i,1,len)RMQ[i][0]=bet[i],bet[i]=i-bet[i]+1;
	fe(j,1,19)for(int i=1;i+(1<<(j-1))-1<=len;++i)RMQ[i][j]=max(RMQ[i][j-1],RMQ[i+(1<<(j-1))][j-1]);
	lg2[1]=0;
	fe(i,2,len)lg2[i]=lg2[i>>1]+1;
}
int main(){
	alf[0].link=-1;
	scanf("%s",s+1),len=strlen(s+1);
	scanf("%s",t+1),lent=strlen(t+1);
	fe(i,1,lent)SAM_insert(t[i]-'a');
	int now=0,cnt=0;
	fe(i,1,len){
		if(alf[now].trans[s[i]-'a'])now=alf[now].trans[s[i]-'a'],cnt++;
		else {
			while(now!=-1&&!alf[now].trans[s[i]-'a'])now=alf[now].link;
			if(now!=-1)cnt=alf[now].len+1,now=alf[now].trans[s[i]-'a'];
			else now=cnt=0;
		}bet[i]=cnt;
	}
	ST_init();
	Q=read();
	fe(i,1,Q){
		int l=read(),r=read();
		if(bet[r]<l)printf("%d\n",r-l+1);
		else if(bet[l]>=l)printf("%d\n",ST_query(l,r));
		else {
			int mid=lower_bound(bet+1,bet+len+1,l)-bet;
			printf("%d\n",max(mid-l,ST_query(mid,r)));
		}
	}
	return 0;
}

7.Len(i) 套DP

例题

还是先求一个 \(Len(i)\) ，然后可以一通乱搞写一个非常经典的枚举断点的DP式 \(f[i]=\max\limits_{j\in[i-len[i],i-1)}\{f[j]+i-j\}\)，发现可以单调队列优化，这个水题就结束了/cy，太水了就不贴代码了。

8.线段树合并维护 Endpos

​ 你要先会线段树合并，不会的话大概花半个小时先学会吧。

​ 然后这题就是大力跑T，然后看每一位是不是可以歪出去，然后挑最远的歪就好了。中间大力转移的时候需要注意走合法的位置，因为要在区间 \([l,r]\) 中，然后可以清晰的知道估计的转移后长度 \(i\) ，于是要求转移到的集合中与区间\([l+i-1,r]\)存在交集。

code

#define fe(i,a,b) for(int i=a;i<=b;++i)
const int MAXN=2e5+5;
int lc[MAXN*20],rc[MAXN*20],siz[MAXN*20],tot_Seg;
inline void upd(int x){siz[x]=siz[lc[x]]+siz[rc[x]];}
int Seg_insert(int l,int r,int g){
	if(l>r)return 0;
	int res=++tot_Seg,mid=(l+r)>>1;
	if(l==r)return siz[res]++,res;
	if(mid>=g)lc[res]=Seg_insert(l,mid,g);
	else rc[res]=Seg_insert(mid+1,r,g);
	return upd(res),res;
}
int merge(int x,int y){
	if(!x||!y)return x+y;
	int res=++tot_Seg;
	lc[res]=merge(lc[x],lc[y]);
	rc[res]=merge(rc[x],rc[y]);
	return upd(res),res;
}
bool query(int x,int l,int r,int L,int R){
	if(l>=L&&r<=R)return siz[x]!=0;
	if(r<L||l>R||!x)return 0;
	int mid=(l+r)>>1;
	return query(lc[x],l,mid,L,R)|query(rc[x],mid+1,r,L,R);
}
char s[MAXN];
struct node{
	int link,len,trans[30];
	int rt,in;//rt代表对应的线段树的根节点，in是入度用来排序
}alf[MAXN*2+1];
int tot_SAM,last,len;
inline void SAM_insert(int c){
	int cur=++tot_SAM,now=last;
	alf[cur].len=alf[last].len+1,alf[cur].rt=Seg_insert(1,len,alf[cur].len);//有所改变的地方
	while(now!=-1&&!alf[now].trans[c])alf[now].trans[c]=cur,now=alf[now].link;
	if(now==-1)alf[cur].link=0;
	else{
		int bet=alf[now].trans[c];
		if(alf[bet].len==alf[now].len+1)alf[cur].link=bet;
		else{
			int clone=++tot_SAM;
			alf[clone]=alf[bet],alf[clone].len=alf[now].len+1,alf[clone].rt=0;
			while(now!=-1&&alf[now].trans[c]==bet)alf[now].trans[c]=clone,now=alf[now].link;
			alf[cur].link=alf[bet].link=clone;
		}
	}
	last=cur;
}
int que[MAXN*2+1],fr,ed;
inline void make_endpos(){
	fe(i,1,tot_SAM)++alf[alf[i].link].in;
	fe(i,1,tot_SAM)if(!alf[i].in)que[ed++]=i;
	while(fr<ed){
		int now=que[fr++];
		if(!now)continue;
		alf[alf[now].link].rt=merge(alf[alf[now].link].rt,alf[now].rt);
		alf[alf[now].link].in--;
		if(!alf[alf[now].link].in)que[ed++]=alf[now].link;
	}
}
int nxt[MAXN];
int main(){
	scanf("%s",s+1);
	len=strlen(s+1);
	alf[0].link=-1;
	fe(i,1,len)SAM_insert(s[i]-'a');
	make_endpos();
	int Q=read();
	while(Q--){
		int l=read(),r=read(),now=0,del,i;
		scanf("%s",s+1),del=strlen(s+1);
		for(i=1;;i++){
			nxt[i]=-1;
			fe(j,max(s[i]-'a'+1,0),'z'-'a')if(alf[now].trans[j]&&query(alf[alf[now].trans[j]].rt,1,len,l+i-1,r)){nxt[i]=j;break;}
			if(i==del+1||!alf[now].trans[s[i]-'a']||!query(alf[alf[now].trans[s[i]-'a']].rt,1,len,l+i-1,r))break;
			now=alf[now].trans[s[i]-'a'];
		}
		while(i&&nxt[i]==-1)i--;
		if(!i)printf("-1\n");
		else {
			fe(j,1,i-1)printf("%c",s[j]);
			printf("%c\n",nxt[i]+'a');
		}
	}
	return 0;
}

四.一些扩展——广义SAM

​ 既然学了SAM就要会广义，不然很亏的\cy

​ 这个东西，网上有很多假写法，主要假在复杂度，要是真的想学可以上OIwiki或者模板题的题解里面看晨星凌写的东西，在线离线都有。顺带一提我现在还只会写离线的，在线的懂了没写。

​ 用我的话来讲，就是先插入一个 tire 树中，然后大力拿 trie 树上面按深度 FIFO 的顺序建SAM，需要注意的是复制节点的地方需要特判一下。复杂度一类的就咕咕了，反正是线性（有些带字符集，想了解可以看15年论文集第一篇，就是在那里提出的）。

CODE

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
#define fe(i,a,b) for(int i=a;i<=b;++i)
inline int read(){
	char ch=getchar();
	int res=0,f=1;
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())res=(res<<3)+(res<<1)+(ch-'0');
	return res*f;
}
const int MAXN=1e6,CSIZ=30;
struct EX_SAM{
	#define pii pair<int,int> 
	#define mp(a,b) make_pair(a,b)
	int tot;
	struct node{int trans[CSIZ+1],link,len;}alf[MAXN*2+1];
	inline void strins(string s){
		int len=s.length(),now=0;
		fe(i,0,len-1)now=alf[now].trans[s[i]-'a']?alf[now].trans[s[i]-'a']:(alf[now].trans[s[i]-'a']=++tot);
	}
	inline long long solve(){
		long long res=0;
		fe(i,1,tot)res+=alf[i].len-alf[alf[i].link].len;
		return res;
	}
	inline void SAM_insert(int last,int c){
		int cur=alf[last].trans[c],now=alf[last].link;
	//	if(alf[cur].len)return ;我觉得这句很没有意义，但是看OIwiki上面有就写在这里以表尊敬，可能是我复杂度假了，反正加不加都能过模板。
		alf[cur].len=alf[last].len+1;
		while(now!=-1&&!alf[now].trans[c])alf[now].trans[c]=cur,now=alf[now].link;
		if(now==-1)alf[cur].link=0;
		else {
			int bet=alf[now].trans[c];
			if(alf[bet].len==alf[now].len+1)alf[cur].link=bet;
			else {
				int clone=++tot;
				alf[clone].link=alf[bet].link,alf[clone].len=alf[now].len+1;
				fe(i,0,CSIZ)if(alf[alf[bet].trans[i]].len)alf[clone].trans[i]=alf[bet].trans[i];
				while(now!=-1&&alf[now].trans[c]==bet)alf[now].trans[c]=clone,now=alf[now].link;
				alf[cur].link=alf[bet].link=clone;
			}
		}
	}
	inline void build(){
		queue<pii> q;
		alf[0].link=-1;
		fe(i,0,CSIZ)if(alf[0].trans[i])q.push(mp(0,i));
		while(!q.empty()){
			int u=alf[q.front().first].trans[q.front().second];
			SAM_insert(q.front().first,q.front().second);
			fe(i,0,CSIZ)if(alf[u].trans[i])q.push(mp(u,i));
			q.pop();
		}
	}
}S;
string s;
int n;
int main(){
	n=read();
	fe(i,1,n){
		cin>>s;
		S.strins(s);
	}
	S.build();
	printf("%lld",S.solve());
	return 0;
}

与 AC自动机

​ 噢，终于来到了我最想写的部分。

​ 在15年论文里面，就提出了 AC自动机可以被 SAM 所代替。但是我没怎么看到实现，于是我自己写了一下，已经把三个luogu的模板题过了。

​ 先来想 AC自动机 和广义 SAM 的关系吧，有好几个相同点。

• 都是以 trie 树作为基础搭建的（这里我说的是离线构造SAM，按晨星凌题解里面说的正确的在线节点数跟离线是一样的，但是我没时间写所以还不得而知）
• 都有一个指向后缀关系的链接/指针（link和fail）

但是还是各有不同点。

​ AC自动机不破坏原来 trie树的结构，但是只能识别一整个串。

​ 广义 SAM 破坏了原来 tire 树的结构，但是可以识别所有的串的所有子串，识别本串当然不在话下。

于是也不是每一个AC自动机的题都可以简单的去替换，比如像阿狸的打字机这种题，既运用了trie树的形态，又运用了fail树的性质的题，虽然我yy了一下可以拿广义 SAM 去写，但是会很烦和恶心，因为原来的结构烂掉了。所以没有必要舍近求远，恶心自己的事情还是少做。

​ 然后具体说说怎么去实现。首先在插入 trie 后，给末尾的状态打上对应的标记。然后就能知道整串在哪里出现。然后对于一整个文本串，直接大力跑，给贪心经过的状态打上标记。

​ 为了避免整串识别到别的串某一后缀去或者说保持逻辑上的合理性，又或是和AC自动机相互照应，反正是需要统计整个子树内的标记情况。然后比AC自动机稍微复杂一点的是当前状态实在囊括了太多信息，所幸模式串串所在的状态的最长串一定是模式串（我 yy 的，感觉上和实践上都是对的，自证感觉不难），所以更关心一个状态的最长串是否被经过。于是需要判断当前贪心得到的最长长度和 \(maxlen\) 的关系。

​ 给出AC自动机模板（二次加强版）的代码。

CODE

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;
#define fe(i,a,b) for(int i=a;i<=b;++i)
inline int read(){
	char ch=getchar();
	int res=0,f=1;
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())res=(res<<3)+(res<<1)+(ch-'0');
	return res*f;
}
const int CHIZ=30,MAXN=4e5;
int ans[MAXN];
struct EX_SAM{
	int tot;
	struct node{
		int trans[CHIZ+1],link,len,vis;
		vector<int>ch,num;
	}alf[MAXN*2+1];
	inline void str_insert(string s,int num){
		int len=s.length(),now=0;
		fe(i,0,len-1)now=alf[now].trans[s[i]-'a']?alf[now].trans[s[i]-'a']:(alf[now].trans[s[i]-'a']=++tot);
		alf[now].num.push_back(num);
	}
	inline void SAM_insert(int last,int c){
		int cur=alf[last].trans[c],now=alf[last].link;
		alf[cur].len=alf[last].len+1;
		while(now!=-1&&!alf[now].trans[c])alf[now].trans[c]=cur,now=alf[now].link;
		if(now==-1)alf[cur].link=0;
		else{
			int bet=alf[now].trans[c];
			if(alf[bet].len==alf[now].len+1)alf[cur].link=bet;
			else{
				int clone=++tot;
				alf[clone].link=alf[bet].link,alf[clone].len=alf[now].len+1;
				fe(i,0,CHIZ)if(alf[alf[bet].trans[i]].len)alf[clone].trans[i]=alf[bet].trans[i];
				while(now!=-1&&alf[now].trans[c]==bet)alf[now].trans[c]=clone,now=alf[now].link;
				alf[cur].link=alf[bet].link=clone;
			}
		}
	}
	inline void build(){
		alf[0].link=-1;
		#define pii pair<int,int>
		#define mp(a,b) make_pair(a,b)
		queue<pii> q;
		fe(i,0,CHIZ)if(alf[0].trans[i])q.push(mp(0,i));
		while(!q.empty()){
			int u=alf[q.front().first].trans[q.front().second];
			SAM_insert(q.front().first,q.front().second);
			q.pop();
			fe(i,0,CHIZ)if(alf[u].trans[i])q.push(mp(u,i));
		}
		fe(i,1,tot)alf[alf[i].link].ch.push_back(i);
	}
	void dfs(int x){
		int siz=alf[x].ch.size();
		fe(i,0,siz-1)dfs(alf[x].ch[i]),alf[x].vis+=alf[alf[x].ch[i]].vis;
		if(alf[x].num.size())fe(i,0,alf[x].num.size()-1)ans[alf[x].num[i]]+=alf[x].vis;
	}
}S;
string s[MAXN];
int main(){
	int n=read();
	fe(i,1,n){
		cin>>s[i];
		S.str_insert(s[i],i);
	}
	S.build();
	cin>>s[0];
	int len=s[0].length(),now=0,cnt=0;
	fe(i,0,len-1){
		if(S.alf[now].trans[s[0][i]-'a'])now=S.alf[now].trans[s[0][i]-'a'],cnt++;
		else{
			while(now!=-1&&!S.alf[now].trans[s[0][i]-'a'])now=S.alf[now].link;
			if(now!=-1)cnt=S.alf[now].len+1,now=S.alf[now].trans[s[0][i]-'a'];
			else now=0,cnt=0;
		}
		if(cnt==S.alf[now].len)S.alf[now].vis++;
		else S.alf[S.alf[now].link].vis++;
	}
	S.dfs(0);
	fe(i,1,n)printf("%d\n",ans[i]);
	return 0;
}

（u1s1,前两个模板是真的水，我拿假写法都写过了，理论上这一个模板比较强，但要是有锅欢迎激情指出，感激不尽）

​ 看到这里可能有人会想，AC自动机这么好写，何必作贱去写 SAM 呢？但是根据15年的论文，广义SAM是可以在线增量构建的。也就是说我可以做一个强制在线的AC自动机，其他的自动机做得到吗？做得到吗？（夜神月基本手势）

​ 只是我暂时没时间写增量构建，但是理论指导实践，我觉得多半是可行的。

​ 希望有一一天能把这个坑填了（ 于2021.2.22 夜 ）