后缀自动机【题目类型总结】

2024-01-21 11:37:46

温馨提示：我很菜，写过的题不多，这里只是介绍一下后缀自动机常用的一些套路。
（以下均假设您已经会 S A M SAM SAM了）
1. 1. 1.找不同子串的个数：
这是 S A M SAM SAM比较常用的技巧， S A M SAM SAM可以用来求这个的原因就是因为 S A M SAM SAM树上不表示相同的串，具体来说有两种方法：
F i r s t : First: First: p a r e n t parent parent树上 D P DP DP求解，求出 s i z [ i ] siz[i] siz[i] ，即以 i i i为根的子树内有多少点。
S e c o n d : Second: Second: ∑ i （ l e n [ i ] − l e n [ f a [ i ] ] ） \sum_{i}（len[i] - len[fa[i]]） ∑i（len[i]−len[fa[i]]），因为每个节点表示的子串都不同，且每个点所表示的子串长度连续，所以 l e n [ i ] − l e n [ f a [ i ] ] len[i] - len[fa[i]] len[i]−len[fa[i]]即为点 i i i表示的子串个数。

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
int last=1,tot=1;
long long f[N],ans;
struct NODE
{
	int fa,len;
	int ch[26];
}node[N];
char s[N];
void insert(int x)
{
	int p=last,np=last=++tot;
	node[np].len=node[p].len+1;
	for(;p&&!node[p].ch[x];p=node[p].fa) node[p].ch[x]=np;
	if(!p) node[np].fa=1;
	else
	{
		int q=node[p].ch[x];
		if(node[q].len==node[p].len+1) node[np].fa=q;
		else
		{
			int nq=++tot;
			node[nq]=node[q];
			node[nq].len=node[p].len+1;
			node[q].fa=node[np].fa=nq;
			for(;p&&node[p].ch[x]==q;p=node[p].fa) node[p].ch[x]=nq;
		}
	}
}
void dfs(int x)
{
	f[x]=1;
	for(int i=0;i<26;i++)
	{
		if(node[x].ch[i])
		 if(!f[node[x].ch[i]])
		  dfs(node[x].ch[i]);
		f[x]+=f[node[x].ch[i]];
	}
	ans+=f[x];
}
int main()
{
	freopen("sam2.in","r",stdin);
	freopen("sam2.out","w",stdout);
	scanf("%s",s+1);
	for(int i=1;s[i];i++)
	insert(s[i]-'a');
	for(int i=2;i<=tot;i++)
	ans+=node[i].len-node[node[i].fa].len;
	cout<<ans;
	return 0;
}

2. 2. 2.判断子串：
直接在 S A M SAM SAM树上跑即可。
3. 3. 3.原串所有子串中字典序第 k k k大（或小）的：
分为两种情况，重复字串算多次还是一次。
如果只算一次的话，那么，先预处理出来 s i z [ i ] siz[i] siz[i] ，然后 d f s dfs dfs直接找。
如果可以算多次的话，就得预处理出每个节点的 e n d p o s endpos endpos集合的大小， e n d p o s endpos endpos集合的大小即为此点表示的所有字符串出现的次数。只要把 s i z [ i ] siz[i] siz[i]的含义改变一下即可。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
char s[N];
bool vis[N];
struct DODE
{
	int len,fa;
	int ch[26];
}node[N];
struct E
{
	int y,nex;
}e[N];
int last=1,tot=1,z,k,head[N],num,f[N],sum[N];
void insert(int x)
{
	int p=last,np=last=++tot;
	f[tot]=1;
	node[np].len=node[p].len+1;
	for(;p&&!node[p].ch[x];p=node[p].fa) node[p].ch[x]=np;
	if(!p) node[np].fa=1;
	else
	{
		int q=node[p].ch[x];
		if(node[q].len==node[p].len+1)
		node[np].fa=q;
		else
		{
			int nq=++tot;
			node[nq]=node[q];
			node[nq].len=node[p].len+1;
			node[np].fa=node[q].fa=nq;
			for(;p&&node[p].ch[x]==q;p=node[p].fa)
			node[p].ch[x]=nq;
		}
	}
}
void dfs(int x,int K)
{
	if(K<=f[x]) return ;
	K-=f[x];
	for(int i=0;i<26;i++)
	{
		if(node[x].ch[i])
		{
			if(K>sum[node[x].ch[i]])
			{
				K-=sum[node[x].ch[i]];
				continue;
			}
			putchar(i+'a');
			dfs(node[x].ch[i],K);
			return;
		}
	}
}
void linjie(int x,int y)
{
	e[++num]=(E){y,head[x]};head[x]=num;
}
void dfs2(int x)
{
	for(int i=head[x];i;i=e[i].nex)
	{
		int y=e[i].y;
		dfs2(y);
		f[x]+=f[y];
	}
}
void dfs3(int x)
{
	if(vis[x]) return;
	vis[x]=1;
	for(int i=0;i<26;i++)
	{
		int y=node[x].ch[i];
		if(!y) continue;
		dfs3(y);
		sum[x]+=sum[y];
	}
}
int main()
{
	freopen("string.in","r",stdin);
	freopen("string.out","w",stdout);
	scanf("%s",s+1);
	cin>>z>>k;
	int n=strlen(s+1);
	for(int i=1;i<=n;i++)
	insert(s[i]-'a');
	for(int i=2;i<=tot;i++)
	linjie(node[i].fa,i);
	dfs2(1);
	for(int i=1;i<=tot;i++)
	{
		sum[i]= z==0?(f[i]=1):f[i];
	}
	f[1]=sum[1]=0;
	dfs3(1);
	if(sum[1]<k)
	{
		cout<<-1;
		return 0;
	}
	dfs(1,k);
	return 0;
}

4. 4. 4.判断两个串 S S S和 P P P的最长公共子串：
先构建出 S S S的后缀树，然后用类似 k m p kmp kmp匹配的方式，用 P P P去匹配。（为什么这里可以用类似 k m p kmp kmp的方法呢？因为后缀树的每一个节点的 f a fa fa都可以表示当前串的第一个 e n d p o s endpos endpos不同的后缀。）
5. 5. 5.判断多个串的最长公共子串长度：
在 4 4 4的基础上，以一个串为模式串建后缀树，其它串匹配，每一次都更新数组，并记录全局最大值，最后输出即可。

#include<bits/stdc++.h>
using namespace std;
const int N=2e4+10;
char s[N];
int last=1,tot=1,now[N],ans[N],sum,n,num,head[N];
struct NODE
{
	int fa,len;
	int ch[26];
}node[N];
struct E
{
	int y,nex;
}e[N];
void insert(int x)
{
	int p=last,np=last=++tot;
	node[np].len=node[p].len+1; 
	for(;p&&!node[p].ch[x];p=node[p].fa) node[p].ch[x]=np;
	if(!p) node[np].fa=1;
	else
	{
		int q=node[p].ch[x];
		if(node[q].len==node[p].len+1) node[np].fa=q;
		else
		{
			int nq=++tot;
			node[nq]=node[q];
			node[nq].len=node[p].len+1;
			node[q].fa=node[np].fa=nq;
			for(;p&&node[p].ch[x]==q;p=node[p].fa) node[p].ch[x]=nq;
		}
	}
}
void linjie(int x,int y)
{
	e[++num]=(E){y,head[x]};head[x]=num;
}
void dfs(int x)
{
	for(int i=head[x];i;i=e[i].nex)
	{
		int y=e[i].y;
		dfs(y);
		now[x]=max(now[y],now[x]);
	}
}
int main()
{
	freopen("lcs.in","r",stdin);
	freopen("lcs.out","w",stdout);
	cin>>n;
	scanf("%s",s);
	for(int i=0;s[i];i++)
	insert(s[i]-'a');
	for(int i=1;i<=tot;i++) ans[i]=node[i].len;
	for(int i=2;i<=tot;i++) linjie(node[i].fa,i);
	for(int i=0;i<n-1;i++)
	{
		scanf("%s",s);
		memset(now,0,sizeof now);
		int p=1,t=0;
		for(int j=0;s[j];j++)
		{
			int c=s[j]-'a';
			while(p>1&&!node[p].ch[c])
			p=node[p].fa,t=node[p].len;
			if(node[p].ch[c]) p=node[p].ch[c],t++;
			now[p]=max(now[p],t);
		}
		dfs(1);
		for(int j=1;j<=tot;j++)
		ans[j]=min(ans[j],now[j]);
	}
	for(int i=1;i<=tot;i++)
	sum=max(sum,ans[i]);
	cout<<sum;
	return 0;
}

6. 6. 6.长度为 k k k的字串中出现次数最多的子串的出现次数：
和 3 3 3类似，用 e n d p o s endpos endpos求出每个点表示子串的出现次数，然后记录当前点表示的子串长度的范围，取 m a x max max。

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
char s[N];
int head[N],last=1,tot=1,num,f[N],ans[N];
struct NODE
{
	int len,fa;
	int ch[26];
}node[N];
struct E
{
	int y,nex;
}e[N];
void linjie(int x,int y)
{
	e[++num]=(E){y,head[x]};head[x]=num;
}
void insert(int x)
{
	int p=last,np=last=++tot;
	f[tot]=1;
	node[np].len=node[p].len+1;
	for(;p&&!node[p].ch[x];p=node[p].fa) node[p].ch[x]=np;
	if(!p) node[np].fa=1;
	else
	{
		int q=node[p].ch[x];
		if(node[q].len==node[p].len+1) node[np].fa=q;
		else
		{
			int nq=++tot;
			node[nq]=node[q];
			node[nq].len=node[p].len+1;
			node[q].fa=node[np].fa=nq;
			for(;p&&node[p].ch[x]==q;p=node[p].fa) node[p].ch[x]=nq;
		}
	}
}
void dfs(int x)
{
	for(int i=head[x];i;i=e[i].nex)
	{
		int y=e[i].y;
		dfs(y);
		f[x]+=f[y];
	}
	ans[node[x].len]=max(ans[node[x].len],f[x]);
}
int main()
{
	freopen("hiho1449.in","r",stdin);
	freopen("hiho1449.out","w",stdout);
	scanf("%s",s+1);
	for(int i=1;s[i];i++) insert(s[i]-'a');
	for(int i=2;i<=tot;i++)
	linjie(node[i].fa,i);
	dfs(1);
	int len=strlen(s+1);
	for(int i=len-1;i>=1;i--) ans[i]=max(ans[i],ans[i+1]);
	for(int i=1;i<=len;i++)
	printf("%d\n",ans[i]);
	return 0;
}

7. 7. 7.一个字符串，依次加进每个字符，求每加入一个字符后，本质不同的子串的个数：
没加入一个字符，会新建一个节点，我们知道，每个节点的 l e n len len减去其 f a fa fa的 l e n len len ，即为本质不同的子串个数，所以我们只需要加上 l e n [ n o w ] − l e n [ f a [ n o w ] ] len[now] - len[fa[now]] len[now]−len[fa[now]]。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
map<int,int > qwq;
const int N=1e5+10;
int n,s[N],m,sa[N],ra[N],fa[N],son[N],x[N],y[N],c[N],height[N];
LL ans,res[N];
int get(int x)
{
	if(qwq[x]==0) qwq[x]=++m;
	return qwq[x];
}
void get_sa()
{
	for(int i=1;i<=n;i++) c[x[i]=s[i]]++;
	for(int i=2;i<=m;i++) c[i]+=c[i-1];
	for(int i=n;i;i--) sa[c[x[i]]--]=i;
	for(int k=1;k<=n;k<<=1)
	{
		int num=0;
		for(int i=n-k+1;i<=n;i++) y[++num]=i;
		for(int i=1;i<=n;i++)
		if(sa[i]>k) y[++num]=sa[i]-k;
		for(int i=1;i<=m;i++) c[i]=0;
		for(int i=1;i<=n;i++) c[x[i]]++;
		for(int i=2;i<=m;i++) c[i]+=c[i-1];
		for(int i=n;i;i--) sa[c[x[y[i]]]--]=y[i],y[i]=0;
		swap(x,y);
		x[sa[1]]=1,num=1;
		for(int i=2;i<=n;i++)
		x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
		if(num==n) break;
		m=num;
	}
}
void get_height()
{
	for(int i=1;i<=n;i++) ra[sa[i]]=i;
	for(int i=1,k=0;i<=n;i++)
	{
		if(ra[i]==1) continue;
		if(k) k--;
		int j=sa[ra[i]-1];
		while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k]) k++;
		height[ra[i]]=k;
	}
}
int main()
{
	freopen("string.in","r",stdin);
	freopen("string.out","w",stdout);
	cin>>n;
	for(int i=n;i>=1;i--) scanf("%d",&s[i]),s[i]=get(s[i]);
	get_sa();
	get_height();
	for(int i=1;i<=n;i++)
	{
		ans+=n-sa[i]+1-height[i];
		fa[i]=i-1;
		son[i]=i+1;
	}
	for(int i=1;i<=n;i++)
	{
		res[i]=ans;
		int o1=ra[i],o2=son[o1],o3=fa[o1];
		ans-=n-sa[o1]+1-height[o1];
		ans-=n-sa[o2]+1-height[o2];
		height[o2]=min(height[o2],height[o1]);
		ans+=n-sa[o2]+1-height[o2];
		son[o3]=o2,fa[o2]=o3;
	}
	for(int i=n;i;i--)
	printf("%lld\n",res[i]);
	return 0;
}

8. 8. 8.求字符串内以 i i i为起点的后缀和以 j j j为起点的后缀的最长公共前缀：
个人感觉这个用 S A SA SA求还是比较直观一点，但用 S A M SAM SAM也不失为一个好方法。严格地说，也不能称之为后缀自动机算法，但是后缀树的构建方法跟后缀自动机差不多，所以归类到这里了。反着建立后缀树，我们知道， p a r e n t parent parent树上， f a fa fa对应的是与当前节点 e n d p o s endpos endpos集合不同的最大后缀，所以，两个节点 i , j i,j i,j的 L C A LCA LCA即表示二者的最长公共后缀，又因为我们是反正建的，所以就是原串的前缀了。
暂时就这些了。

码农公寓

相关文章