本文主要是介绍模板：广义SAM（字符串），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

所谓广义SAM，就是更广泛意义下的SAM

（逃）

前言

感觉字符串的理解难度的巅峰还是在SAM，广义SAM只是在套一些特判罢了，并不是太难理解。
可以解决多字符串的子串问题，几乎就是把SAM能做的东西从单串变成了多串。

解析

在线做法

有一个很流行的盗版做法是每次加入新串时把 l s t lst lst 重新赋值为 1 1 1，然后就和正常SAM一样做。
但这会出现一些问题，就是当 t r a n s l s t , c trans_{lst,c} translst,c​ 存在时，我们会加入空节点。
这里的空节点的具体含义是指其 m i n l e n > m a x l e n minlen>maxlen minlen>maxlen，从而使得该结点代表的等价类没有任何字符串。
这个时候我们进行特判即可，后面还是按照正常SAM做。

struct SAM{
	int tr[N][26],fa[N],len[N],tot,lst;
	SAM(){tot=lst=1;}
	
	inline int ins(int c,int p){
		c-='a';
		if(tr[p][c]){
			int q=tr[p][c];
			if(len[q]==len[p]+1) return q;
			else{
				int nq=++tot;
				len[nq]=len[p]+1;fa[nq]=fa[q];
				for(int i=0;i<26;i++) tr[nq][i]=tr[q][i];
				fa[q]=nq;
				for(;p&&tr[p][c]==q;p=fa[p]) tr[p][c]=nq;
				return nq;
			}
		}
		else{
			int cur=++tot;len[cur]=len[p]+1;
			for(;p&&!tr[p][c];p=fa[p]) tr[p][c]=cur;
			if(!tr[p][c]) fa[cur]=1;
			else{
				int q=tr[p][c];
				if(len[q]==len[p]+1) fa[cur]=q;
				else{
					int nq=++tot;
					len[nq]=len[p]+1;fa[nq]=fa[q];
					for(int i=0;i<26;i++) tr[nq][i]=tr[q][i];
					fa[q]=fa[cur]=nq;
					for(;p&&tr[p][c]==q;p=fa[p]) tr[p][c]=nq;
				}
			}
			return cur;
		}
	}
	inline void addstring(char *s){
		int n=strlen(s+1),lst=1;
		for(int i=1;i<=n;i++) lst=ins(s[i],lst);
		return;
	}
}sam;

然而，这个做法对一棵 t r i e trie trie 树建SAM的时候复杂度是 O ( G ( T ) ) O(G(T)) O(G(T)) 的（ G ( T ) G(T) G(T) 表示所有叶子的深度和），这在许多时候会被卡成 O ( n 2 ) O(n^2) O(n2)，因此，我们需要寻找另一种做法。

离线做法

这个方法对于 t r i e trie trie 树建SAM的复杂度是优秀的 O ( T ) O(T) O(T)。
考虑bfs，从而使得深度单调不降。
每次取出队首，以它父亲在SAM上对应的结点 作为 l s t lst lst 进行插入即可。由于 t r i e trie trie 树本身的性质，此时必然有 t r a n s l s t , c = N U L L trans_{lst,c}=NULL translst,c​=NULL，因此直接按照正常的SAM写即可。

struct SAM{
	int tr[N][26],pos[N],len[N],fa[N],tot;
	
	SAM(){tot=1;}
	
	inline int ins(int c,int p){
		int cur=++tot;
		len[cur]=len[p]+1;
		for(;p&&!tr[p][c];p=fa[p]) tr[p][c]=cur;
		if(!tr[p][c]) fa[cur]=1;
		else{
			int q=tr[p][c];
			if(len[q]==len[p]+1) fa[cur]=q;
			else{
				int nq=++tot;
				len[nq]=len[p]+1;fa[nq]=fa[q];
				for(int i=0;i<26;i++) tr[nq][i]=tr[q][i];
				fa[q]=fa[cur]=nq;
				for(;p&&tr[p][c]==q;p=fa[p]) tr[p][c]=nq;
			}
		}
		return cur;
	}
	
	int q[N],st,ed;
	void build(){
		q[st=ed=1]=1;
		pos[1]=1;
		while(st<=ed){
			int now=q[st++];
			//pos[now]=ins(trie.col[now],pos[trie.fa[now]]);
			for(int i=0;i<26;i++){
				int to=trie.tr[now][i];
				if(to){
					q[++ed]=to;
					pos[to]=ins(trie.col[to],pos[now]);
				}
			}
		}
		return;
	}
}sam;

这篇关于模板：广义SAM（字符串）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！