首页 > 其他分享 >初探后缀自动机

初探后缀自动机

时间：2024-05-29 21:44:52浏览次数：34  
标签：cur SAM 后缀 len int sam 初探 自动机 节点

本篇旨在讲解部分常见的 SAM 技巧，以及经典的 SAM 题目。

几点暴论：

  • 如果题目中求的是什么子串的出现次数，那直接无脑上 SAM。因为 SAM 的 parent 树是反串的后缀树，求出现次数时，二者并无区别。
  • 如果题目中涉及了「前缀」「后缀」等字样，请仔细品味在使用 SAM 时是否应该对反串建 parent 树。

废案：

Luogu P3804 【模板】后缀自动机（SAM）

我们发现 SAM 几乎可以当作子串的 AC 自动机。

将 SAM 上的每个前缀节点的权值置为 \(1\)。那么类似地，对于 SAM 上的一个节点，统计其在 link 树上的子树和。那么，该等价类中的每个字符串，出现次数均为该子树和。

原因如下：根据 endpos 的定义，SAM 上所有前缀节点互不相同。同时，该前缀必然作为其所在等价类中的最长串。因此，不会出现某个该等价类的字符串没出现次数的情况（最长串都出现了，更短的串必然出现）。

# include <bits/stdc++.h>

const int N=2000010;

struct Node{
	int ch[26],link,len;
}sam[N];
int cnt=1;
char s[N];
int n;
int siz[N];
std::vector <int> G[N];

long long ans;

inline int sam_extend(int last,int c){
	int cur=++cnt,p=last;
	sam[cur].len=sam[last].len+1;
	siz[cur]=1;
	while(!sam[p].ch[c]) sam[p].ch[c]=cur,p=sam[p].link;
	if(!p){
		sam[cur].link=1;
		return cur;
	}
	int q=sam[p].ch[c];
	if(sam[p].len+1==sam[q].len){
		sam[cur].link=q;
		return cur;
	}
	int clone=++cnt;
	sam[clone]=sam[q],sam[clone].len=sam[p].len+1;
	while(p&&sam[p].ch[c]==q) sam[p].ch[c]=clone,p=sam[p].link;
	sam[cur].link=sam[q].link=clone;
	return cur;
}

void dfs(int i){
	for(auto v:G[i]) dfs(v),siz[i]+=siz[v];
	if(siz[i]>1) ans=std::max(ans,1ll*siz[i]*sam[i].len);
	return;
}

int main(void){
	scanf("%s",s+1);
	n=strlen(s+1);
	int last=1;
	for(int i=1;i<=n;++i){
		last=sam_extend(last,s[i]-'a');
	}
	for(int i=2;i<=cnt;++i) G[sam[i].link].push_back(i);
	dfs(1);
	printf("%lld",ans);
	return 0;
}

Luogu P4070 [SDOI2016] 生成魔咒

即，需要 SAM 支持：末端插入字符，在线询问本质不同子串数。

考察哪些串是新的本质不同子串。事实上，只有在 \(i\) 这个位置第一次出现的串才是新的本质不同子串。那么答案就呼之欲出了：找到 \(s[1,i]\) 的前缀节点，该等价类中的节点数量即为答案。

# include <bits/stdc++.h>

const int N=100010,INF=0x3f3f3f3f;

struct Node{
	int len,link;
	std::map <int,int> nex;
}sam[N*2];

char s[N];
int n;
int last=1;
int tot=1;
long long ans;

inline int read(void){
	int res,f=1;
	char c;
	while((c=getchar())<'0'||c>'9')
		if(c=='-')f=-1;
	res=c-48;
	while((c=getchar())>='0'&&c<='9')
		res=res*10+c-48;
	return res*f;
}
inline void sam_extend(int c){
	int now=++tot,p=last;
	sam[now].len=sam[last].len+1;
	last=now;
	while(p&&(!sam[p].nex[c]))
		sam[p].nex[c]=now,p=sam[p].link;
	if(!p){
		sam[now].link=1;
		return;
	}
	int qnode=sam[p].nex[c];
	if(sam[p].len+1==sam[qnode].len){
		sam[now].link=qnode;
		return;
	}
	int clone=++tot;
	sam[clone]=sam[qnode];
	sam[clone].len=sam[p].len+1;
	sam[qnode].link=clone,sam[now].link=clone;
	while(p&&sam[p].nex[c]==qnode){
		sam[p].nex[c]=clone,p=sam[p].link;
	}
	return;
}
int main(void){
	n=read();
	for(int i=1;i<=n;++i){
		int x=read();
		sam_extend(x);
		ans+=sam[last].len-sam[sam[last].link].len;
		printf("%lld\n",ans);
	}
	return 0;
}

Luogu P3975 [TJOI2015] 弦论

考虑利用 SAM 的 DAG 结构解决。注意到性质：SAM 上从起始节点开始沿 DAG 行走，路径形成的字符串必然是字符串的子串，且所有子串都可以被某条路径形成，且不会有不同路径形成相同字符串。

据此可以贪心。设 \(f(i)\) 表示，从 \(i\) 号节点出发，可以走出的字符串数量。另记 \(g(i)\) 表示从 \(i\) 号节点出发，可以走出的空字符串数量（即 \(i\) 走到 \(i\)）。

现在考虑从起始节点开始行走，设当前位于 \(i\)。若 \(k \leq g(i)\)，则字符串就是当前路径。否则，从小大大枚举出边 \((i,j)\)，并判断：

  • 若 \(k \leq f(j)\)，则路径必然经过边 \((i,j)\)，记录下 \((i,j)\) 上的字符，停止枚举，并将 \(i\) 移动到 \(j\)。
  • 若 \(k > f(j)\)，则经过 \((i,j)\) 的数量不足 \(k\)，因此将 \(k\) 减去 \(f(j)\)。

当 \(T = 0\) 时，只有本质不同子串算作不同。那么有 \(g(i) = 1\)，\(f(i)\) 可以拓扑排序得出。

当 \(T = 1\) 时，位置不同子串算不同，那么有 \(g(i)\) 等于 \(i\) 的 endpos 集合大小，可以 link 树上 DP 得出。

# include <bits/stdc++.h>

const int N=1000010,INF=0x3f3f3f3f;

struct Node{
	int link,len,nex[26];
}sam[N];
int tot=1,last=1;
int n,T,k;
int esize[N]; // 文中的 g 数组
char s[N];
long long f[N];
std::vector <int> G[N];

inline int read(void){
	int res,f=1;
	char c;
	while((c=getchar())<'0'||c>'9')
		if(c=='-')f=-1;
	res=c-48;
	while((c=getchar())>='0'&&c<='9')
		res=res*10+c-48;
	return res*f;
}
inline void sam_extend(int c){
	int now=++tot,p=last;
	esize[now]=1;
	sam[now].len=sam[last].len+1,last=now;
	while(p&&!sam[p].nex[c]){
		sam[p].nex[c]=now,p=sam[p].link;
	}
	if(!p){
		sam[now].link=1;
		return;
	}
	int qnode=sam[p].nex[c];
	if(sam[qnode].len==sam[p].len+1){
		sam[now].link=qnode;
		return;
	}
	int clone=++tot;
	sam[clone]=sam[qnode],sam[clone].len=sam[p].len+1,sam[qnode].link=sam[now].link=clone;
	while(p&&sam[p].nex[c]==qnode) sam[p].nex[c]=clone,p=sam[p].link;
	return;
}
void dfs_esize(int i){
	for(auto to:G[i]){
		dfs_esize(to),esize[i]+=esize[to];
	}
	return;
}
long long dfs(int i){
	if(f[i]) return f[i];
	f[i]=esize[i];
	for(int j=0;j<26;++j){
		int to=sam[i].nex[j];
		if(to)  f[i]+=dfs(to);
	}
	return f[i];
}
void solve(int i,int resk){
	if(resk<=esize[i]) return;
	resk-=esize[i];
	for(int j=0;j<26;++j){
		int to=sam[i].nex[j];
		if(!to) continue;
		if(resk>f[to]){
			resk-=f[to];
			continue;
		}
		putchar('a'+j),solve(to,resk);
		return;
	}
	return;
}
int main(void){
	scanf("%s",s+1);
	n=strlen(s+1),T=read(),k=read();
	for(int i=1;i<=n;++i) sam_extend(s[i]-'a');
	for(int i=2;i<=tot;++i) G[sam[i].link].push_back(i);
	if(T) dfs_esize(1);
	else
		for(int i=1;i<=tot;++i) esize[i]=1;
	esize[1]=0,dfs(1);
	if(k>f[1]) printf("-1");
	else{
		solve(1,k);
	}
	return 0;
}

Luogu P4248 [AHOI2013] 差异

直接对正串做是较为困难的，因为 SAM 构建的整个过程都没有刻画过后缀节点。

考虑将串取反，所求即为所有前缀节点对的在 link 树上的距离之和。可以 DFS link 树解决。

# include <bits/stdc++.h>

const int N=500010,INF=0x3f3f3f3f;

inline int read(void){
	int res,f=1;
	char c;
	while((c=getchar())<'0'||c>'9')
		if(c=='-') f=-1;
	res=c-48;
	while((c=getchar())>='0'&&c<='9')
		res=res*10+c-48;
	return res*f;
}
char s[N];
int n;

struct Node{
	int link,nex[26],len;
}sam[N*2];

int last=1,cnt=1;
int siz[N*2];

inline void extend(int c){
	int cur=++cnt,p=last,q;
	sam[cur].len=sam[p].len+1,last=cur,siz[cur]=1;
	while(p&&!sam[p].nex[c]) sam[p].nex[c]=cur,p=sam[p].link;
	if(!p) return sam[cur].link=1,void();
	q=sam[p].nex[c];
	if(sam[p].len+1==sam[q].len) return sam[cur].link=q,void();
	int clone=++cnt;
	sam[clone]=sam[q],sam[clone].len=sam[p].len+1,sam[cur].link=sam[q].link=clone;
	while(p&&sam[p].nex[c]==q) sam[p].nex[c]=clone,p=sam[p].link;
	return;
}
long long ans;
std::vector <int> G[N*2];

void dfs(int x){
	for(auto y:G[x]) dfs(y),siz[x]+=siz[y],ans+=1ll*(sam[y].len-sam[x].len)*(n-siz[y])*siz[y];
	return;
}

inline void init(void){
	for(int i=2;i<=cnt;++i){
		G[sam[i].link].push_back(i);
	}
	dfs(1);
	return;
}

int main(void){
	scanf("%s",s+1),n=strlen(s+1);
	for(int i=n;i;--i) extend(s[i]-'a');
	init();
	printf("%lld",ans);

	return 0;
}

Codeforces 653F Paper task

建出 SAM，考虑对于某个等价类一起处理。

对于某个等价类，找出其任意一 endpos，设该等价类中的字符串左端点 \(s\) 位于 \([l,r]\)，右端点为 \(t\)。那么合法括号串应当满足后缀和非负（将左括号看作 \(-1\)，右括号看作 \(1\)），区间和为 \(0\) 两个条件。注意到后缀和非负相当于给左端点提出了下界限制，这可以二分 + ST 表求出。区间和为 \(0\) 可以转后缀和后变为端点 \(s\) 处和端点 \(t+1\) 处后缀相等。将同一后缀和的端点放入 vector，lower_bound 和 upper_bound 即可求出合法 \(s\) 端点数量。

# include <bits/stdc++.h>

const int N=1000010,INF=0x3f3f3f3f;

inline int read(void){
	int res,f=1;
	char c;
	while((c=getchar())<'0'||c>'9')
		if(c=='-') f=-1;
	res=c-48;
	while((c=getchar())>='0'&&c<='9')
		res=res*10+c-48;
	return res*f;
}

struct Node{
	int link,len,nex[2],edp;
}sam[N];
int n;
char s[N];
int cnt=1,last=1;

inline void extend(int c,int i){
	int cur=++cnt,p=last;
	sam[cur].len=sam[last].len+1,last=cur,sam[cur].edp=i;
	while(p&&!sam[p].nex[c]) sam[p].nex[c]=cur,p=sam[p].link;
	if(!p) return sam[cur].link=1,void();
	int q=sam[p].nex[c];
	if(sam[p].len+1==sam[q].len) return sam[cur].link=q,void();
	int clone=++cnt;
	sam[clone]=sam[q],sam[clone].len=sam[p].len+1,sam[cur].link=sam[q].link=clone;
	while(p&&sam[p].nex[c]==q) sam[p].nex[c]=clone,p=sam[p].link;
	return;
}
std::vector <int> G[N];
void dfs(int x){
	for(auto y:G[x]) dfs(y),sam[x].edp=sam[x].edp?sam[x].edp:sam[y].edp;
	return;
}

int S[N];
int mx[N][20];

inline void st_init(void){
	for(int i=1;i<=n;++i) mx[i][0]=S[i];
	for(int j=1;(1<<j)<=n;++j)
		for(int i=1;i+(1<<j)-1<=n;++i) mx[i][j]=std::min(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);	
	return;
}
inline int qu(int l,int r){
	int k=std::__lg(r-l+1);
	return std::min(mx[l][k],mx[r-(1<<k)+1][k]);
}

inline int getmin(int l,int r,int x){
	int ans=0;
	while(l<=r){
		int mid=(l+r)>>1;
		if(qu(mid,x)<S[x+1]) ans=mid,l=mid+1;
		else r=mid-1;
	}
	return ans;
}
std::unordered_map <int,std::vector <int> > vec;

inline int getans(int l,int r,int x){
	if(l>r) return 0;
	auto tl=std::lower_bound(vec[x].begin(),vec[x].end(),l);
	auto tr=std::upper_bound(vec[x].begin(),vec[x].end(),r);
	return tr-tl;
}

int main(void){
//	freopen("in.txt","r",stdin);
	
	n=read();
	scanf("%s",s+1);
	for(int i=1;i<=n;++i) extend(s[i]-'(',i);
	for(int i=n;i;--i) S[i]=S[i+1]+((s[i]=='(')?-1:1);
	for(int i=1;i<=n;++i) vec[S[i]].push_back(i);
	for(int i=2;i<=cnt;++i) G[sam[i].link].push_back(i);
	dfs(1);
	
	st_init();
	long long ans=0;
	
	for(int i=2;i<=cnt;++i){
		int pos=sam[i].edp,lenl=sam[sam[i].link].len+1,lenr=sam[i].len;		
		int l=getmin(1,pos,pos)+1;
		ans+=getans(std::max(l,pos-lenr+1),pos-lenl+1,S[pos+1]);
	}
	
	printf("%lld",ans);

	return 0;
}

LOJ6071「2017 山东一轮集训 Day5」字符串

贪心一定不劣。对于一个串 \(t\)，如果我们能够在某个 \(s_i\) 中匹配，那么一定不会提前转入 \(s_{i+1}\)。

对 \(s_i\) 建出 SAM。完善其 DAG 结构，具体地，对于 \(s_i\) 的 SAM 中某个节点的出边 \(tr_i(x,c)\)，若其不存在则令其转到最小的 \(j\) 使得 \(s_j\) 中存在字符 \(c\)。最后在 DAG 上 DP 即可。

SP1812 LCS2 - Longest Common Substring II

并不需要建出广义 SAM。考虑对其中一个串建出 SAM，并像 AC 自动机上匹配一样，将其它串放在 SAM 上遍历，维护其它所有串在 SAM 上的匹配长度。每个节点的最终匹配长度即为该节点在每个串上的匹配长度的最小值。

具体地，对于每个其它串 \(T\)，匹配过程如下：

  • 维护变量 \(len,cur\)，表示 SAM 上匹配的长度。初始值为 \(len = 0,cur = 1\)。
  • 遍历 \(i = 1,2,\cdots,|T|\)，检查 \(tr(cur,T_i)\) 是否存在。
    • 若存在，则令 \(len\) 增加 \(1\)，\(cur\) 转到 \(tr(cur,T_i)\)。
    • 若不存在，则遍历 \(cur\) 的后缀链接，直到存在 \(T_i\) 的转移边，或到达根为止。若 \(tr(cur,T_i)\) 存在，则将 \(len\) 置为 \(cur\) 的节点长度加 \(1\)，将 \(cur\) 转到 \(tr(cur,T_i)\)。否则，令 \(len \leftarrow 0,cur \leftarrow 1\)。

考虑到 \(n \leq 10\)，因此这种做法是可以通过的。另外，如果我们选取最短的串建立 SAM，设其串长为 \(l\)，那么复杂度为 \(O(L|\Sigma| + l\cdot \frac{L}{l}) = O(L|\Sigma|)\)，因此 \(n\) 更大时该做法仍然成立。

# include <bits/stdc++.h>

const int N=200010,INF=0x3f3f3f3f;
struct Node{
	int len,link,nex[26];
}sam[N];
int tot=1,last=1;
char s[N];
int mx[N],himx[N],n;
int cnt[N],od[N];

inline int read(void){
	int res,f=1;
	char c;
	while((c=getchar())<'0'||c>'9')
		if(c=='-')f=-1;
	res=c-48;
	while((c=getchar())>='0'&&c<='9')
		res=res*10+c-48;
	return res*f;
}
inline void sam_extend(int c){
	int now=++tot,p=last;
	sam[now].len=sam[last].len+1,last=now;
	while(p&&!sam[p].nex[c]) sam[p].nex[c]=now,p=sam[p].link;
	if(!p){
		sam[now].link=1;
		return;
	}
	int qnode=sam[p].nex[c];
	if(sam[p].len+1==sam[qnode].len){
		sam[now].link=qnode;
		return;
	}else{
		int clone=++tot;
		sam[clone]=sam[qnode],sam[clone].len=sam[p].len+1,sam[now].link=sam[qnode].link=clone;
		while(p&&sam[p].nex[c]==qnode) sam[p].nex[c]=clone,p=sam[p].link;
	}
	return;
}
inline void chkmax(int &x,int v){
	x=std::max(x,v);
	return;
}
int main(void){
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=1;i<=n;++i) sam_extend(s[i]-'a');
	for(int i=1;i<=tot;++i) himx[i]=sam[i].len;
	for(int i=1;i<=tot;++i) ++cnt[sam[i].len];
	for(int i=1;i<=tot;++i) cnt[i]+=cnt[i-1];
	for(int i=1;i<=tot;++i) od[cnt[sam[i].len]--]=i;

	while(~scanf("%s",s+1)){
		n=strlen(s+1);
		memset(mx,0,sizeof(mx));
		int len=0,cur=1;
		for(int i=1;i<=n;++i){
			int c=s[i]-'a';
			if(sam[cur].nex[c]) cur=sam[cur].nex[c],++len,chkmax(mx[cur],len);
			else{
				while(cur&&!sam[cur].nex[c]) cur=sam[cur].link;
				if(!cur) len=0,cur=1;
				else len=sam[cur].len+1,cur=sam[cur].nex[c],chkmax(mx[cur],len);
			}
		}
		for(int i=tot;i;--i) chkmax(mx[sam[od[i]].link],mx[od[i]]);
		for(int i=1;i<=tot;++i) himx[i]=std::min(himx[i],mx[i]);
	}
	int ans=0;
	for(int i=1;i<=tot;++i) chkmax(ans,himx[i]);
	printf("%d",ans); 
	return 0;
}

Codeforces 235C Cyclical Quest

对原串 \(S\) 建出 SAM，考虑每个询问串 \(T\)。对于循环移位，我们有经典的处理方法：将 \(\text{rev}(T)\) 拼接到 \(T\) 之后，那么对于每个 \(|T| < i \leq 2|T|\)，\([i-|T|+1,i]\) 就是一个循环移位。

采用上一题类似的匹配方法。但本题中，我们任何时刻都不应当让匹配长度超过 \(|T|\)，同时两个本质相同的循环移位不应当被计算多次。因此匹配流程如下：

  • 维护变量 \(len,cur\)，表示 SAM 上匹配的长度。初始值为 \(len = 0,cur = 1\)。

  • 遍历 \(i = 1,2,\cdots,2|T|\)，并执行：

    1. 检查 \(tr(cur,T_i)\) 是否存在。

      若存在，则令 \(len\) 增加 \(1\)，\(cur\) 转到 \(tr(cur,T_i)\)。

      若不存在，则遍历 \(cur\) 的后缀链接，直到存在 \(T_i\) 的转移边，或到达根为止。若 \(tr(cur,T_i)\) 存在，则将 \(len\) 置为 \(cur\) 的节点长度加 \(1\)，将 \(cur\) 转到 \(tr(cur,T_i)\)。否则，令 \(len \leftarrow 0,cur \leftarrow 1\)。

    2. 检查匹配长度 \(len\) 是否大于 \(|T|\)。若是，则将 \(len\) 减小 \(1\)，若此行为使得 \(len\) 不再属于 \(cur\) 的长度区间，则 \(cur\) 变为 \(\text{link}(cur)\)。

    3. 若 \(i>|T|\)，检查匹配长度 \(len\) 是否恰好为 \(|T|\)，且 \(cur\) 节点没有被打上标记 \(T\)。若是，则答案累加上 \(cur\) 节点的 endpos 集合大小，并给 \(cur\) 节点打上标记 \(T\)，防止被重复计算。

# include <bits/stdc++.h>

const int N=2000010,INF=0x3f3f3f3f;

inline int read(void){
	int res,f=1;
	char c;
	while((c=getchar())<'0'||c>'9')
		if(c=='-') f=-1;
	res=c-48;
	while((c=getchar())>='0'&&c<='9')
		res=res*10+c-48;
	return res*f;
}

struct Node{
	int link,len,nex[26],edp;
}sam[N];
int n;
char s[N];
int cnt=1,last=1;
int siz[N];

inline void extend(int c){
	int cur=++cnt,p=last;
	sam[cur].len=sam[last].len+1,last=cur,siz[cur]=1;
	while(p&&!sam[p].nex[c]) sam[p].nex[c]=cur,p=sam[p].link;
	if(!p) return sam[cur].link=1,void();
	int q=sam[p].nex[c];
	if(sam[p].len+1==sam[q].len) return sam[cur].link=q,void();
	int clone=++cnt;
	sam[clone]=sam[q],sam[clone].len=sam[p].len+1,sam[cur].link=sam[q].link=clone;
	while(p&&sam[p].nex[c]==q) sam[p].nex[c]=clone,p=sam[p].link;
	return;
}
std::vector <int> G[N];
void dfs(int x){
	for(auto y:G[x]) dfs(y),siz[x]+=siz[y];
	return;
}
int tag[N];

int main(void){
	scanf("%s",s+1),n=strlen(s+1);
	for(int i=1;i<=n;++i) extend(s[i]-'a');
	for(int i=2;i<=cnt;++i) G[sam[i].link].push_back(i);
	dfs(1);
	memset(tag,-1,sizeof(tag));
	
	int T=read();
	while(T--){
		scanf("%s",s+1);
		int m=strlen(s+1);
		int len=0,cur=1;
		long long ans=0;
		
		for(int i=1;i<=2*m;++i){
			int c=(i<=m)?s[i]-'a':s[i-m]-'a';
			if(sam[cur].nex[c]) cur=sam[cur].nex[c],++len;
			else{
				while(cur&&!sam[cur].nex[c]) cur=sam[cur].link;
				if(!cur) len=0,cur=1;
				else len=sam[cur].len+1,cur=sam[cur].nex[c];
			}
			if(len>m&&((--len)==sam[sam[cur].link].len)) cur=sam[cur].link;			
			if(i<=m||tag[cur]==T||len!=m) continue;
			tag[cur]=T;
			ans+=siz[cur];
		}
		printf("%lld\n",ans);	
	}
	return 0;
}

P6640 [BJOI2020] 封印

设 \(f(i)\) 表示 \(s[i,n]\) 和 \(t\) 的 LCP 长度，使用 SAM 或 SA 容易求出。

考虑答案为

\[\max\limits_{i=l}^{r} \{\min(f(i),r-i+1)\} \]

使用二分答案规避掉内层的 min。具体地，设当前二分的答案为 \(x\)，那么我们只检查 \(r-i + 1 \geq x\) 的部分中 \(f(i)\) 的值是否大于等于 \(x\)。

P4770 [NOI2018] 你的名字

线段树合并其一

Codeforces 1037H Security

线段树合并其二

Codeforces 1276F Asterisk Substrings

注意到答案形如：\(s,s*,*t,s*t,*\)。

考虑分类讨论。对于 \(*\)，贡献为 \(1\)。对于 \(s\) 型的答案，当且仅当 \(s\) 是原串 \(S\) 的子串时合法，容易建 SAM 求出；对于 \(s*\) 型的答案，则要求 \(s\) 是原串前缀 \([1,|S|-1]\) 的子串，对于 \(*t\) 型的答案，要求 \(t\) 是原串后缀 \([2,|S|]\) 的子串，这些可以分别在原串和反串上建 SAM 求出。

现在考虑形如 \(s*t\) 的串。\(s\) 需要是 \(S\) 的子串，因此考虑 \(S\) 的子串构成的等价类，等价类中的每个字符串，可以选择的 \(t\) 数量是相同的。设该等价类的 endpos 集合为 \(E\)，那么对于任意 \(e \in E\)，后缀 \(S[e+2,|S|]\) 中的每个前缀都可以作为合法的 \(t\)。将反串 SAM 上的前缀节点 \(|S| - (e+2) + 1\) 到根的路径打上标记，那么所有被标记的边长之和即为答案。

可以使用线段树合并的方法维护每个等价类被打上标记节点的边长之和。对于每个等价类，我们将被打上标记的节点按照 DFS 序顺序记录在线段树中。根据经典结论，合并时，该子树内的答案等于左子树合并后的答案，加上右子树合并后的答案，再减去左子树中最靠右的节点和右子树最靠左的节点的 LCA 深度。

P4218 [CTSC2010] 珠宝商

  • 朴素暴力

    枚举每个节点作为根。统计从该节点开始的路径数量，从根往下 DFS，维护根到当前节点形成的字符串在 SAM 上对应的节点 \(cur\)，每到一个点，答案累加上 \(cur\) 节点的 endpos 集合大小。若某一时刻该字符串不再在 SAM 中，则返回。时间复杂度 \(O(n^2)\)。

  • 另类暴力

    枚举每个节点 \(r\) 作为根。统计经过该节点的路径数量，考虑路径 \(s \to r \to t\)，拆成两部分 \(s \to r\) 和 \(r \to t\)。设 \(f(p)\) 表示有多少 \(s \to r\) 的字符串在特征串 \(E\) 中在位置 \(p\) 结束，\(g(p)\) 表示有多少 \(r \to t\) 的字符串在特征串 \(E\) 中在位置 \(p\) 开始。

    \(g(p)\) 可以通过反转 \(E\) 后，在 \(f(p)\) 中类似的算法求出。现在只需要考虑求出 \(f\)。

    对于所有路径 \(s \to r\)，如果它在 SAM 上匹配后位于的节点 \(cur\)，那么我们将 \(cur\) 节点的权值加上 \(1\)。最后自上往下遍历 fail 树，将儿子的权值加上父亲的权值即可。最后对于每个 \(p\)，取出 \(s[1,p]\) 对应节点的权值，即为 \(f(p)\)。

    因此现在重点在于求出 \(cur\)。设有边 \((u,v)\)，其中 \(u\) 是 \(v\) 的父亲。\(u \to r\) 的字符串为 \(S\)，在 SAM 上匹配的节点为 \(cur\)，那么字符串会从 \(S\) 变为 \(S' = c_v+ S\)。考察 \(cur\) 的变化：

    • 若 \(S\) 不为 \(cur\) 等价类中的最长串，则检查等价类中长度为 \(|S'|\) 的字符串是否恰为 \(S'\)。若是，则 \(cur\) 不变，否则 \(S'\) 没有出现在 \(E\) 中，返回。随意求得 \(cur\) 的某个 endpos \(R(cur)\)，则只需要检查是否有 \(c_v = E[R(cur)-|S'| + 1]\)。

    • 若 \(S\) 为 \(cur\) 等价类中的最长串，则 \(c_v + S\) 所属等价类只能为 \(cur\) 在 fail 树上的某个儿子。检查 \(cur\) 在 fail 树上是否存在儿子 \(nex\)，使得 \(c_v=E[R(nex) - \text{len}(cur)]\)。这样的儿子可以预处理得出。

      若存在，则 \(cur\) 转到 \(nex\)。否则 \(S'\) 没有出现在 \(E\) 中，返回。

    最后，注意到贡献可以来源于同一子树。贡献可删除，因此要再 DFS 某个子树，删除子树的相互贡献。

    该暴力的时间复杂度为 \(O(n|E|)\)。

考虑点分治结合另类暴力。当子树大小不超过 \(\sqrt{|E|}\) 时，采用朴素暴力，否则采用另类暴力。则时间复杂度为 \(O(n \log n \sqrt{|E|})\)。

SP687 REPEATS - Repeats

注意到 border 和周期是对应的，而周期和整周期有很强的联系。

建立 SAM。对于每个等价类，设该 endpos 中相邻 endpos 的最小差为 \(d\)，若最长串 \(len\) 满足 \(len \geq d\)，则该等价类能够做出的最大贡献为 \(\lfloor \frac{len+d}{d} \rfloor\)。

使用线段树合并求出 endpos 最小差即可。

Luogu P4482 [BJWC2018] Border 的四种求法

所求即最大的 \(i \in [l,r)\) 使得 \(\text{lcp}(s[1,i],s[1,r]) \geq i-l+1\)。

在 SAM 的 link 树上标记出所有前缀节点。对于询问 \([l,r]\)，记 \(s[1,x]\) 对应节点为 \(ed_x\)，则 \(i\) 需要满足的第二条限制可以写作 \(\text{dep}(\text{lca}(ed_i,ed_r)) \geq i-l+1\)。枚举 \(u = \text{lca}(ed_i,ed_r)\)，则对于 \(i\) 的限制形如 \(i< dep_u + l,i \in [l,r)\)。link 树树高为线性，直接遍历 \(ed_r\) 的所有祖先，复杂度 \(O(n)\)，难以通过。

考虑树链剖分。对于每条重链考虑，此时合法的 \(u\) 是这条重链的一个前缀。设该前缀为链顶 \(top\) 到某个节点 \(x\)，则 \(i\) 的来源有三种情况：

  1. \(i\) 对应的节点位于 \(x\) 子树内。

  2. \(i\) 对应的节点位于重链链顶到 \(x\) 这一段。

  3. \(i\) 对应的节点位于重链链顶到 \(x\) 这一段的某个节点的轻子树中。

对于情况 \(1\)，此时的 \(dep_u\) 就是 \(dep_x\)。（如果实际的 LCA 深度更深，则会在更靠下的重链中被正确计算贡献。实际贡献是更大的，因此不需要担心这里计算错误）对 SAM 上节点做可持久化线段树合并，则容易在 \(x\) 的线段树中查询出最大的 \(i\) 满足 \(i< dep_x + l,i \in [l,r)\)。

对于情况 \(2\) 和情况 \(3\)，从链头开始，依次加入重链上的节点 \(t\) 以及 \(t\) 的轻子树到一棵线段树中，直到 \(x\) 为止（包括 \(x\)）。具体地，加入某个节点时，若它是代表前缀 \([1,d]\) 的节点，则在线段树上的位置 \(d\) 插入值 \(d - dep_t\)。最后，线段树上查询所有小于 \(r\) 的位置中，值 \(d - dep_t\) 小于 \(l\) 的最大位置是多少。若该位置不小于 \(l\)，则它可以作为一个合法的 \(i\)。

该做法的优势在于，如果有多组询问，我们可以离线下来，将对于某段重链的查询挂在节点 \(x\) 上，然后整体利用同一棵线段树计算答案。假设 \(n,q\) 同阶，则处理询问的复杂度为 \(O(n \log^2 n)\) 。现在考虑对于情况 \(2,3\)，遍历重链和轻子树的复杂度。根据重链剖分的性质，全体重链的长度和为 \(n\)，全体重链轻子树的大小为 \(O(n \log n)\)。那么，一共只会有 \(O(n \log n)\) 次加点，从而这部分的复杂度也是 \(O(n \log ^2 n)\)。这样，我们便在 \(O(n \log ^2n)\) 的时间复杂度，\(O(n \log^2 n)\) 或 \(O(n \log n)\)（采用更高明的线段树合并）的空间复杂度内解决了本题。

P6816 [PA2009] Quasi-template

见 题解 Luogu P6816 [PA2009] Quasi-template - Meatherm。

P6292 区间本质不同子串个数

考虑类似 HH 的项链的套路，区间数颜色问题我们钦定每个点都在最后出现的位置贡献。离线 + 扫描线，考虑右端点 \(r\) 往右移一个位置到 \(r+1\)，所对应到的前缀节点为 \(u\)，那么 \(u\) 和 \(u\) Parent 树上所有祖先的出现位置都会变成 \(r+1\)。如果一个串 \(T\) 最后一次出现的位置为 \(p\)，那么 \(l \in [1,|T| - p + 1]\) 的 \(l\) 的答案就会加上 \(1\)。

这非常像 LCT 的 access 操作，于是我们就用 LCT 来维护这个东西。在 access 时，首先需要删掉这条链之前的贡献，再加入新的贡献。考虑 Parent 树上任意一条垂直链所代表的字符串长度连续，即：\(|T| \in [L,R]\)，因此对 \(l\) 的答案的贡献形式是区间加等差数列。因为只需要单点查询，考虑差分之后变成区间加法，线段树维护即可。

悲惨故事 长文警告 关于广义 SAM 的讨论 - 洛谷 | 计算机科学教育新生态 (luogu.com)

关于广义 SAM：。

Codeforces 452E Three strings

广义 SAM 其零

JZPGYZ - Sevenk Love Oimaster

广义 SAM 其一

P4022 [CTSC2012]熟悉的文章

记字典为 \(D\)。对于一个询问串 \(S\)，考虑二分答案 \(L\)。设 \(f(i)\) 表示前 \(i\) 个字符最多能匹配上多少个，则当 \(f(|S|) \geq 0.9 |S|\) 时，答案 \(L\) 合法，否则非法。

考虑如何求出 \(f(i)\)。设 \(l_i\) 表示 \(S[1,i]\) 的最长后缀长度使得 \(S[i - l_i + 1,i]\) 作为 \(D\) 中某个串的子串出现过。则 \(f(i) = \max(f(i-1),\max\limits_{j=i-l_i}^{i-L} f(j) + i-j)\)。根据 \(l_i\) 的定义，显然 \(i - l_i\) 单调不降（若 \(i- l_i < (i-1) - l_{i-1}\)，则 \(l_i > l_{i-1} +1\)，矛盾）同时 \(i-L\) 单调不降，因此这是左右端点均不降的滑动窗口问题，使用单调队列优化 DP 解决。

只需要将 \(S\) 在 \(D\) 的广义 SAM 上匹配即可求出 \(l_i\)。这个过程是线性的，因此总复杂度为线性对数。

Luogu P3346 [ZJOI2015] 诸神眷顾的幻想乡

广义 SAM 其二

P4081 [USACO17DEC] Standing Out from the Herd P

广义 SAM 其三

Codeforces 666E Forensic Examination

广义 SAM 其四

标签：cur,SAM,后缀,len,int,sam,初探,自动机,节点
From： https://www.cnblogs.com/Meatherm/p/18221137

相关文章

  • AI助力科研：自动化科学构思生成系统初探
    科学研究作为推动创新和知识进步的关键活动，在解决复杂问题和提升人类生活水平方面发挥着至关重要的作用。然而，科学研究的固有复杂性、缓慢的进展速度以及对专业专家的需求，限制了其生产力的提升。为了增强科研效率，本文提出了一个名为ResearchAgent的系统，这是一个由大型语言模型（L......
  • Redis之初探
    Redis是什么Redis是一个开源，内存存储的数据结构服务器，可用作数据库，高速缓存和消息队列代理。Key-Value格式的缓存和存储服务器；数据结构服务器，它支持字符串、哈希表、列表、集合、有序集合，位图，hyperloglogs等数据类型;所有数据集必须在内存中使用,磁盘是用来持久数据的。是一......
  • linux shell中移除文件的后缀、前缀
     001、[root@PC1test2]#a="a.csv.map.txt"[root@PC1test2]#echo$aa.csv.map.txt[root@PC1test2]#echo${a%.*}a.csv.map[root@PC1test2]#echo${a%%.*}a 。 002、[root@PC1test2]#ls[root@PC1test2]#a="a.csv.map.txt"[root@......
  • 【元胞自动机】基于元胞自动机模拟社会力模型解决人员疏散问题附Matlab代码
    【元胞自动机】基于元胞自动机模拟社会力模型解决人员疏散问题附Matlab代码首先,元胞自动机(CellularAutomata,简称CA)是一种离散动力系统,由一个规则化的网络组成,每个元胞根据自身状态和周围邻居元胞的状态更新自身状态。CA模型已被广泛应用于模拟各种复杂系统,包括人群......
  • 【初探Java之路 六 】集合1-ArrayList和LinkedList的使用与源码分析
    ......
  • PWN系列-初探IO
    PWN系列-初探IO记录一下自己理解的IO，文章的代码均是glibc-2.23版本下的代码。由于笔者才疏学浅，学识有限，文章中难免会有疏漏和错误之处，恳请各位师傅批评指正，多多包涵。什么是IOIO中的I其实就是in，O其实就是out，一个输入，一个输出。IO长什么样子_IO_FILE_plus首先先来认识一下_I......
  • 递归地获取当前目录下所有文件的后缀名（不重复）
    好的，这里是修改后的批处理脚本，它将递归地获取当前目录下所有文件的后缀名，并将不重复的后缀名输出到当前目录下的a.txt文件中，然后结束：@echooffsetlocalenabledelayedexpansion::初始化一个空的集合用来存储后缀名set"suffixList="::递归遍历当前目录及其子目录下的所......
  • 后缀数组（SA）
    后缀数组(SA)并非指数字的后缀，而针对字符串而生的算法。字符串的后缀指是指从某个位置开始到整个串末尾结束的一个特殊子串。后缀排序将所有后缀按照字典序排序，利用计数排序时间+倍增复杂度为\(O(nlogn)\) 。\(sa[i]:\)排名为\(i\)的后缀的起始位置。\(rk[i]:\)起始位置为\(......
  • (转载)数据结构-02 中缀表达式转后缀表达式并计算值
    1.图解中缀表达式转后缀表达式通过 数据结构-01-图解后缀表达式值计算方式 我们了解到后缀表达式（例如：931-3*+102/+）对计算机运算的方便，但是它却让我们这些人类十分的难受，因此我们需要在设计一个，中缀表达式转后缀表达式的程序来一劳永逸. 规则：依次遍历表达式，1.如......
  • (转载)数据结构-01-图解后缀表达式值计算方式
    目录:数据结构-01-图解后缀表达式值计算方式数据结构-02图解中缀表达式转后缀表达式并计算值1.简介问题：我们平常使用的数学表达式大多数是“中缀表达式”例如：9+(3-1)×3+10÷2，对人比较友好，但是这个对计算机计算并不友好，因为计算机无法智能判断运算顺序的问题（比如说乘法加......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99