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

作者:神秘网友 发布时间:2021-02-22 19:20:16

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

[学习笔记] 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;//最大串长度,后缀链接,出现次数(后文会讲)
	mapchar , 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!=-1alf[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;
	vectorint 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!=-1alf[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-(1k)+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[i1]+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(lr)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=Lr=R)return siz[x]!=0;
	if(rL||lR||!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!=-1alf[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(fred){
		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(inxt[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

#includeiostream
#includecstdio
#includealgorithm
#includecstring
#includecmath
#includequeue
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=(res3)+(res1)+(ch-'0');
	return res*f;
}
const int MAXN=1e6,CSIZ=30;
struct EX_SAM{
	#define pii pairint,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!=-1alf[now].trans[c]==bet)alf[now].trans[c]=clone,now=alf[now].link;
				alf[cur].link=alf[bet].link=clone;
			}
		}
	}
	inline void build(){
		queuepii 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){
		cins;
		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

#includeiostream
#includecstdio
#includealgorithm
#includecstring
#includecmath
#includequeue
#includevector
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=(res3)+(res1)+(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;
		vectorintch,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!=-1alf[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 pairint,int
		#define mp(a,b) make_pair(a,b)
		queuepii 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){
		cins[i];
		S.str_insert(s[i],i);
	}
	S.build();
	cins[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 夜 )

[学习笔记] SAM——后缀自动机 相关文章

  1. LeetCode 41. 缺失的第一个正数

    新手学习中,有任何错误或者更好地方法、思路欢迎指教! #Array 6 题目难度: 困难 题目描述: 给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。进阶:你可以实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案吗示例 1:输

  2. 基于android的app开发!Android之内存泄漏调试学习与总结,深度好文

    一,鸿蒙核心内容掌握程度 看看下面这些鸿蒙知识点你掌握了多少: 基础环境和开发工具 开发工具安装 运行开发工具完成基础配置DevEco Studio 运行第一个hello world 运行第一个页面 通过代码创建页面 Feature Ability 编程实现页面跳转 市面上的鸿蒙教程大多

  3. 安卓入门开发教程!作为移动开发程序员应该怎样去规划自己的学习路线含泪整理面经

    前言 今年的寒来得格外慢,眼看年关将近,开年就入春了,但西北季风似乎没有往年的无情。 天气和互联网行业的双重寒冷险些让我翻不过身。 那时的我正处在一个尴尬的境地,工作两年,压力不大,朝九晚五,做着一些在刚入职就一直在做的增删改查。 曾经也找过

  4. android游戏开发培训班!Android学习路线指南,醍醐灌顶!

    前言 如果你也学习Android,那么你大概率会看过我的文章。经常有读者给我留言: “该怎么学习Android”、“日常学习Android的方法是什么”。 所以,今天,我将献上 一份《Android知识图谱》 ,以自身的经验 所见所闻,旨在告诉大家, 学习Android,实际上需

  5. android视频开发!Android学习笔记在互联网上火了,终获offer

    雪上加霜 本人一名Android程序员,今年29岁了。大厂小厂都呆过,现在在腾讯工作!明明工作顺利,家庭和睦儿女成全,但是总是会感觉到,一股无形的压力,推着我走!作为一名程序员我最怕的不是996,也是写不完的代码,而是怕过了我的黄金年龄,社会责任家庭责

  6. segmentation_models_pytorch库学习

    AugustMe的学习小课堂2020-10-20 10:22:33912收藏1分类专栏:PyTorch图像分割版权 segmentation_models_pytorch是一个基于PyTorch的图像分割神经网络 这个新集合由俄罗斯的程序员小哥Pavel Yakubovskiy一手打造。 github地址:https://github.com/qubvel/seg

  7. 《Javascript核心DOM、BOM操作》笔记

    Javascript核心DOM、BOM操作(pink老师),笔记 目标:能获得页面元素、给元素注册事件、操作元素的属性、创建元素、操作DOM节点。 console.dir(input等元素对象) ,打印对象所有方法和属性。 事件三要素 :事件源、事件类型、事件处理程序 事件执行步骤; 1.

  8. HTML学习笔记

    html5 什么是html:(hyper text markup language) 超文本标记语言 w3c :万维网联盟 网页基本信息 一些快捷方式:br+ tab == / ......... !-- 这是注释 --!-- DOCTYPE 告诉浏览器我们需要使用的规范 --!-- 快捷键 ctrl + / :注释快捷方式--!DOCTYPE htmlhtml l

  9. Nginx 入门学习笔记

    Nginx 为什么使用Nginx 随着平台的用户越来越多,并发量慢慢的增大,一台服务器已经满足不了我们的需求. 什么是Nginx Nginx (engine x) 是一个高性能的HTTP和反向代理web服务器,同时也提供了IMAP/POP3/SMTP服务。Nginx是由伊戈尔·赛索耶夫为俄罗斯访问量第二

  10. 学习下Redis这个核心数据类型

    string 字符串 tring 类型是二进制安全的,即 string 中可以包含任何数据。 Redis 中的普通 string 采用 raw encoding 即原始编码方式,该编码方式会动态扩容,并通过提前预分配冗余空间,来减少内存频繁分配的开销。 在字符串长度小于 1MB 时,按所需长度的

每天更新java,php,javaScript,go,python,nodejs,vue,android,mysql等相关技术教程,教程由网友分享而来,欢迎大家分享IT技术教程到本站,帮助自己同时也帮助他人!

Copyright 2020, All Rights Reserved. Powered by 跳墙网(www.tqwba.com)|网站地图|关键词