首页 > 其他分享 >后缀自动机的一些题目的整理

后缀自动机的一些题目的整理

时间：2024-03-28 18:24:57浏览次数：258  
标签：ch 题目 fa 后缀 len int np nq 自动机

后缀自动机的一些题目的整理

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

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

板子题，没啥好说的。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e6+5;

int tot=1,last=1,idx,n;
int ver[N],h[N],ne[N];
char s[N];
ll f[N],ans;
struct node
{
	int len,fa;
	int ch[26];
}a[N];

void extend(int c)
{
	int p=last,np=++tot;
	last=np;
	f[tot]=1;
	a[np].len=a[p].len+1;
	while(p&&!a[p].ch[c])
	{
		a[p].ch[c]=np;
		p=a[p].fa;
	}
	if(!p) a[np].fa=1;
	else 
	{
		int q=a[p].ch[c];
		if(a[q].len==a[p].len+1) a[np].fa=q;
		else 
		{
			int nq=++tot;
			a[nq]=a[q];
			a[nq].len=a[p].len+1;
			a[q].fa=a[np].fa=nq;
			while(p&&a[p].ch[c]==q) 
			{
				a[p].ch[c]=nq;
				p=a[p].fa;
			}
		}
	}
}
void add(int x,int y)
{
	ver[++idx]=y,ne[idx]=h[x],h[x]=idx;
}
void dfs(int u)
{
	for(int i=h[u];i;i=ne[i])
	{
		dfs(ver[i]);
		f[u]+=f[ver[i]];
	}
	if(f[u]>1) ans=max(ans,f[u]*a[u].len);
}
int main ()
{
	cin>>s;
	n=strlen(s);
	for(int i=0;i<n;i++) extend(s[i]-'a');
	for(int i=2;i<=tot;i++) add(a[i].fa,i);
	dfs(1);
	cout<<ans<<"\n";
	return 0;
}

P5231 [JSOI2012] 玄武密码

P5231 [JSOI2012] 玄武密码

类似于 \(trie\) 的查找，比较简单。

#include <bits/stdc++.h>
using namespace std;
const int N=1e7+5;
int n,m;
int tot=1,last=1;
struct node
{
	int len,fa;
	int ch[4];
}a[N*2];
char s[N];
string ss;
void extend(int c)
{
	int p=last,np=++tot;
	last=np;
	a[np].len=a[p].len+1;
	while(p&&!a[p].ch[c])
	{
		a[p].ch[c]=np;
		p=a[p].fa;
	}
	if(!p) a[np].fa=1;
	else 
	{
		int q=a[p].ch[c];
		if(a[q].len==a[p].len+1) a[np].fa=q;
		else 
		{
			int nq=++tot;
			a[nq]=a[q];
			a[nq].len=a[p].len+1;
			a[q].fa=a[np].fa=nq;
			while(p&&a[p].ch[c]==q) 
			{
				a[p].ch[c]=nq;
				p=a[p].fa;
			}
		}
	}
}
map<char,int> ma;
int main ()
{
	ma['N']=0,ma['S']=1,ma['W']=2,ma['E']=3;
	cin>>n>>m;
	scanf("%s",s);
	for(int i=0;s[i];i++) extend(ma[s[i]]);
	while(m--)
	{
		scanf("%s",s);
		int p=1,ret=0;
		for(int i=0;s[i];i++)
		{
			int t=ma[s[i]];
			if(a[p].ch[t]) p=a[p].ch[t],ret++;
			else break;
		}
		cout<<ret<<"\n";
	}
	return 0;
}

P5341 [TJOI2019] 甲苯先生和大中锋的字符串

P5341 [TJOI2019] 甲苯先生和大中锋的字符串

求出现 \(k\) 次的子串中出现次数的最多的长度。

用差分数组统计出现的次数。

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,t,k,ans;
int tot=1,last=1;
int f[N],d[N];
struct node
{
	int len,fa;
	int ch[26];
}a[N];
char s[N];
void extend(int c)
{
	int p=last,np=++tot;
	last=np;
	f[tot]=1;
	a[np].len=a[p].len+1;
	while(p&&!a[p].ch[c])
	{
		a[p].ch[c]=np;
		p=a[p].fa;
	}
	if(!p) a[np].fa=1;
	else 
	{
		int q=a[p].ch[c];
		if(a[q].len==a[p].len+1) a[np].fa=q;
		else 
		{
			int nq=++tot;
			a[nq]=a[q];
			a[nq].len=a[p].len+1;
			a[q].fa=a[np].fa=nq;
			while(p&&a[p].ch[c]==q) 
			{
				a[p].ch[c]=nq;
				p=a[p].fa;
			}
		}
	}
}
int ver[N],ne[N],h[N],idx;
void add(int x,int y)
{
	ver[++idx]=y,ne[idx]=h[x],h[x]=idx;
}
void dfs(int x)
{
	for(int i=h[x];i!=-1;i=ne[i])
	{
		dfs(ver[i]);
		f[x]+=f[ver[i]];
	}
	if(f[x]==k&&a[x].len) d[a[a[x].fa].len+1]++,d[a[x].len+1]--;
}
void clear()
{
	tot=last=1;
	idx=0;
	ans=-1;
	memset(d,0,sizeof d);
	memset(a,0,sizeof a);
	memset(f,0,sizeof f);
	memset(h,-1,sizeof h);
}
void solve()
{
	clear();
	cin>>s;
	n=strlen(s);
	cin>>k;
	for(int i=0;s[i];i++) extend(s[i]-'a');
	for(int i=2;i<=tot;i++) add(a[i].fa,i);
	dfs(1);
	int mx=1;
	for(int i=0;s[i];i++) 
	{
		d[i+1]+=d[i];
		if(d[i+1]>=mx)
		{
			mx=d[i+1];
			ans=i+1;
		}
	}
	if(ans==0) ans=-1;
	cout<<ans<<"\n";
}
int main ()
{
	cin>>t;
	while(t--) solve();	
	return 0;
}

LONGCS - Longest Common Substring

LONGCS - Longest Common Substring

对第一个字符串建立 \(SAM\)，然后让后面的字符串在上面跑。类似于 \(KMP\)，不匹配就跳到父亲，匹配就往下跳，并更新答案。最后拓扑排序统计答案。

#include <bits/stdc++.h>
using namespace std;
const int N=2e4+5;

int n,m;
int tot=1,last=1;
struct node
{
	int len,fa;
	int ch[26];
}a[N];
int ans[N],now[N];
int ver[N],ne[N],h[N],idx;
char s[N];
void extend(int c)
{
	int p=last,np=++tot;
	last=np;
	a[np].len=a[p].len+1;
	while(p&&!a[p].ch[c])
	{
		a[p].ch[c]=np;
		p=a[p].fa;
	}
	if(!p) a[np].fa=1;
	else 
	{
		int q=a[p].ch[c];
		if(a[q].len==a[p].len+1) a[np].fa=q;
		else 
		{
			int nq=++tot;
			a[nq]=a[q];
			a[nq].len=a[p].len+1;
			a[q].fa=a[np].fa=nq;
			while(p&&a[p].ch[c]==q) 
			{
				a[p].ch[c]=nq;
				p=a[p].fa;
			}
		}
	}
}
void add(int x,int y)
{
	ver[++idx]=y,ne[idx]=h[x],h[x]=idx;
}
void dfs(int x)
{
	for(int i=h[x];i!=-1;i=ne[i])
	{
		dfs(ver[i]);
		now[x]=max(now[x],now[ver[i]]);
	}
}
void solve()
{
	tot=1,last=1,idx=0;
	memset(a,0,sizeof a);
	cin>>n;
	cin>>s;
	for(int i=0;s[i];i++) extend(s[i]-'a');
	for(int i=1;i<=tot;i++) ans[i]=a[i].len;
	memset(h,-1,sizeof h);
	for(int i=2;i<=tot;i++) add(a[i].fa,i);
	for(int i=1;i<n;i++)
	{
		cin>>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&&!a[p].ch[c]) p=a[p].fa,t=a[p].len;
			if(a[p].ch[c]) p=a[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]);
	}
	int res=0;
	for(int i=1;i<=tot;i++) res=max(res,ans[i]);
	cout<<res<<"\n";
}
int main ()
{
	int t;
	cin>>t;
	while(t--) solve();
	return 0;
}

NSUBSTR - Substrings

NSUBSTR - Substrings

求长度为 \(x\) 的子串的最大出现次数。

不需要用数据结构来处理 \(RMQ\)，只需要倒着统计就行了。

因为一个字符串如果包含最长的字串有\(|endpos(u)|\)次，那么它包含更短的子串肯定有\(|endpos(u)|\)次

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int tot=1,last=1;
struct node
{
	int len,fa;
	int ch[26];
}a[N];
char s[N];
int f[N],ans[N];
void extend(int c)
{
	int p=last,np=++tot;
	last=np;
	f[tot]=1;
	a[np].len=a[p].len+1;
	while(p&&!a[p].ch[c])
	{
		a[p].ch[c]=np;
		p=a[p].fa;
	}
	if(!p) a[np].fa=1;
	else 
	{
		int q=a[p].ch[c];
		if(a[q].len==a[p].len+1) a[np].fa=q;
		else 
		{
			int nq=++tot;
			a[nq]=a[q];
			a[nq].len=a[p].len+1;
			a[q].fa=a[np].fa=nq;
			while(p&&a[p].ch[c]==q) 
			{
				a[p].ch[c]=nq;
				p=a[p].fa;
			}
		}
	}
}
int ver[N],ne[N],h[N],idx;
void add(int x,int y)
{
	ver[++idx]=y,ne[idx]=h[x],h[x]=idx;
}
void dfs(int x)
{
	for(int i=h[x];i!=-1;i=ne[i])
	{
		dfs(ver[i]);
		f[x]+=f[ver[i]];
	}
	ans[a[x].len]=max(ans[a[x].len],f[x]);
}
int main ()
{
	cin>>s;
	int n=strlen(s);
	for(int i=0;s[i];i++) extend(s[i]-'a');
	memset(h,-1,sizeof h);
	for(int i=2;i<=tot;i++) add(a[i].fa,i);
	dfs(1);
	for(int i=n;i>=1;i--) ans[i]=max(ans[i],ans[i+1]);
	for(int i=1;i<=n;i++) cout<<ans[i]<<"\n";
	return 0;
}

P3975 [TJOI2015] 弦论

P3975 [TJOI2015] 弦论

建立 \(SAM\) 后从根开始往后跑，\(dfs\) 统计该节点后面存在的自串的数量。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
ll n,k,t;
char s[N];
int tot=1,last=1;
struct node
{
	int len,fa;
	int ch[26];
}a[N];
ll f[N],siz[N];
void extend(int c)
{
	int p=last,np=++tot;
	last=np;
	siz[np]=1;
	a[np].len=a[p].len+1;
	while(p&&!a[p].ch[c])
	{
		a[p].ch[c]=np;
		p=a[p].fa;
	}
	if(!p) a[np].fa=1;
	else 
	{
		int q=a[p].ch[c];
		if(a[q].len==a[p].len+1) a[np].fa=q;
		else 
		{
			int nq=++tot;
			a[nq]=a[q];
			a[nq].len=a[p].len+1;
			a[q].fa=a[np].fa=nq;
			while(p&&a[p].ch[c]==q)
			{
				a[p].ch[c]=nq;
				p=a[p].fa;
			}
		}
	}
}
int ver[N],ne[N],h[N],idx;
void add(int x,int y)
{
	ver[++idx]=y,ne[idx]=h[x],h[x]=idx;
}
void dfs1(int x)
{
	for(int i=h[x];i;i=ne[i])
	{
		int y=ver[i];
		dfs1(y);
		siz[x]+=siz[y];
	}
	f[x]=siz[x];
}
int vis[N];
ll dfs2(int x)
{
	if(vis[x]) return f[x];
	vis[x]=1;
	for(int i=0;i<26;i++)
	{	
		int y=a[x].ch[i];
		if(y) f[x]+=dfs2(y);
	}
	return f[x];
}
void query(int x,ll k)
{
	if(k<=siz[x]) return ;
	k-=siz[x];
	for(int i=0;i<26;i++)
	{
		int y=a[x].ch[i];
		if(k>f[y]) k-=f[y];
		else 
		{
			cout<<(char)('a'+i);
			query(y,k);
			return ;
		}
	}
}
int main ()
{
	cin>>s;
	n=strlen(s);
	cin>>t>>k;
	if(n*(n+1)/2<k) 
	{
		cout<<-1<<"\n";
		return 0;
	}
	for(int i=0;s[i];i++) extend(s[i]-'a');
	for(int i=2;i<=tot;i++) add(a[i].fa,i);
	if(t) dfs1(1);
	else for(int i=1;i<=tot;i++) f[i]=siz[i]=1;
	f[1]=siz[1]=0;
	dfs2(1);
	query(1,k);
	return 0;
}

P3649 [APIO2014] 回文串

P3649 [APIO2014] 回文串

最恶心的一道题，\(manacher+SAM+倍增\)，这样子写应该有黑题的难度，只是因为这题是回文自动机的板子题，所以是紫题。

\(manacher\) 找到回文串后在 \(SAM\) 上找出现次数。可以从根开始跑到回文串的 \(endpos\)，但这样复杂度为平方级。于是考虑倍增向上跳，往上跳是到当前字符串的后缀上，所以查 \((l.r)\)，从 \(r\) 开始往上跳。

代码细节非常的多。

#include <bits/stdc++.h>
using namespace std;
const int N=6e5+5;
typedef long long ll;
int tot=1,last=1;
int n,m;
int p[N];
int st[N][20],lg[N],d[N],id[N],tp[N>>1];
int f[N];
ll ans;
char s[N>>1],t[N];
struct node
{
	int fa,len;
	int ch[26];
}a[N];
void extend(int c,int x)
{
	int p=last,np=++tot;
	last=np;
	f[tot]=1;
	tp[x]=tot;
	a[np].len=a[p].len+1;
	while(p&&!a[p].ch[c]) a[p].ch[c]=np,p=a[p].fa;
	if(!p) a[np].fa=1;
	else 
	{
		int q=a[p].ch[c];
		if(a[q].len==a[p].len+1) a[np].fa=q;
		else 
		{
			int nq=++tot;
			a[nq]=a[q];
			a[nq].len=a[p].len+1;
			a[q].fa=a[np].fa=nq;
			while(q&&a[p].ch[c]==q) a[p].ch[c]=nq,p=a[p].fa;
		}
	}
}
void check(int l,int r)
{
	if(l<1||r>n||l>r) return ;
	int pos=tp[r];
	for(int i=lg[d[pos]];i;i--)
	{
		int x=st[pos][i];
		if(a[x].len>=r-l+1) pos=x;
	}
	ans=max(ans,1ll*f[pos]*(r-l+1));
}
void manacher()
{
	t[++m]='&';
	for(int i=1;i<=n;i++) t[++m]='#',t[++m]=s[i],id[m]=i;
	t[++m]='#';
	t[++m]='*';
	int mid=0,mr=0;
	for(int i=1;i<=m;i++)
	{
		if(i<mr) p[i]=min(p[2*mid-i],mr-i);
		else p[i]=1;
		check(id[i-p[i]+2],id[i+p[i]-2]);
		while(t[i+p[i]]==t[i-p[i]]) p[i]++,check(id[i-p[i]+2],id[i+p[i]-2]);
		if(p[i]+i>mr)
		{
			mr=p[i]+i;
			mid=i;
		}
	}
}
int c[N],b[N];
void build()
{
	for(int i=1;i<=n;i++) extend(s[i]-'a',i);
	for(int i=1;i<=tot;i++) c[a[i].len]++;
	for(int i=1;i<=n;i++) c[i]+=c[i-1];
	for(int i=1;i<=tot;i++) b[c[a[i].len]--]=i;
	for(int i=tot;i;i--) f[a[b[i]].fa]+=f[b[i]];
	for(int i=2;i<=tot;i++) lg[i]=lg[i>>1]+1;
	for(int i=1;i<=tot;i++)
	{
		int pos=b[i],fa=a[pos].fa;
		d[pos]=d[fa]+1;
		st[pos][0]=fa;
		for(int j=1;(1<<j)<=d[pos];j++) st[pos][j]=st[st[pos][j-1]][j-1];
	}	
	
}
int main ()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	build();
	manacher();
	cout<<ans<<"\n";
	return 0;
}

标签：ch,题目,fa,后缀,len,int,np,nq,自动机
From： https://www.cnblogs.com/zhouruoheng/p/18102335

相关文章

  • 软考中级软件设计师【结构化开发】知识点+题目
      一、耦合   耦合是模块之间的相对独立性（相互连接的紧密程度）的度量。耦合取决于各个模块之间接口的复杂程度、调用模块的方式以及通过接口的信息类型等，有以下几个类型。   无直接耦合：指两个模块之间没有直接关系，它们分别属于不同模块的控制和调用，它们之间不......
  • 数据结构与算法题目集（中文）6-1 单链表逆转 C语言
    6-1单链表逆转本题要求实现一个函数，将给定的单链表逆转。函数接口定义：ListReverse(ListL);其中List结构定义如下：typedefstructNode*PtrToNode;structNode{ElementTypeData;/*存储结点数据*/PtrToNodeNext;/*指向下一个结点的指针*/};t......
  • 《自动机理论、语言和计算导论》阅读笔记：p49-p67
    《自动机理论、语言和计算导论》学习第4天，p49-p67总结，总计19页。一、技术总结1.DeterministicFiniteAutomata(DFA)vsNondeterministicFiniteAutomata(NFA)(1)DFA定义(2)NFA定义A"nonedeterministic"finiteautomatahasthepowertobeinseveralstatesatonce......
  • word批量添加后缀名的方法有哪些？看这里就够了
    在日常办公和学习中，我们经常需要处理大量的Word文档。有时候，为了更好地组织和管理这些文档，或者为了满足特定的需求，我们可能需要给这些Word文档批量添加后缀。当我们拥有大量的Word文档时，如何有效地分类和管理这些文档成为了一个重要的问题。通过给Word文档批量添加后缀，我们可以......
  • 题目思考过程简记
    ARC175C题解题目链接我们考虑经典套路，假设前\(i-1\)个数已经被确定。设\(f_k(x)\)表示\(a_k=x\)时\(\sum_{i=k+1}^n|\a_i-a_{i-1}\|\)的最小值。那么，\(a_i=x\)当且仅当\(x\)取最小值且\(|\x-a_{i-1}\|+f_i(x)\)为所有可能中的最......
  • PTA基础编程题目集 6-10 阶乘计算升级版
    阶乘计算升级版本题要求实现一个打印非负整数阶乘的函数。函数接口定义：voidPrint_Factorial(constintN);其中N是用户传入的参数，其值不超过1000。如果N是非负整数，则该函数必须在一行中打印出N!的值，否则打印“Invalidinput”。裁判测试程序样例：#include<stdio.h>......
  • 华为OD机试 - 2024真题目录
    真题目录专栏介绍100分题目录200分题目录专栏介绍专栏中的所有博客均有详细的题目描述、输入、输出、测试使用、备注等描述，有算法源码可直接使用，计划每道题目的源码有Python、C++、C、javascript等，持续更新最新题目、不同语言的解答方法，目前Python源码居多。100分......
  • 自动生成小学四则运算题目的命令行程序
    这个作业属于哪个课程软件工程2024(广东工业大学)这个作业要求在哪里结对项目这个作业的目标学习完成项目的过程正文一、姓名、学号、GitHub本次项目缺失队友，由个人完成。崔海源3122004779github地址二、PSP表格PSP2.1PersonalSoftwareProcessStag......
  • 歌曲后缀解释
    linst.(Instruments)1offvoca：歌曲的无人声演奏版，即伴奏Explicit(简称E)：脏版/脏标（脏话未过滤）Clean/radioversion：净版/消音版，脏话被过滤的版本，与Explict相对Acoustic：歌曲不插电版本，不含电子合成音乐，而是由纯乐队演奏Feat./ft.(featuring)：携手某某联合打造Prelude：前奏......
  • c语言编程题目：水仙花数
    题目：水仙花数是指一个N位正整数（N>=3），它的每位上的数字的N次幂之和等于它本身。例如：153=1^3+5^3+3^3。要求：计算所有N位水仙花数。给出一个正整数N（3<=N<=7），按递增顺序输出所有水仙花数，每个数字占一行。编程思路分析：输入一个正整数N。N为位数，N=3就表明是3位数。判断N位......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99