首页 > 其他分享 >后缀自动机的应用

后缀自动机的应用

时间:2023-07-30 21:23:27浏览次数:42  
标签:fa 后缀 siz sum len int 应用 -- 自动机

后缀自动机的原理就不在赘述了,这里主要介绍它的应用。

板子:

struct node{
	int c[26],len,fa;
} a[maxn];
void build(int x){
	int p=las;int np=las=++tot;
	a[np].len=a[p].len+1;
	for(;p&&!a[p].c[x];p=a[p].fa)
		a[p].c[x]=np;
	if(!p)
		a[np].fa=1;
	else{
		int q=a[p].c[x];
		if(a[q].len==a[p].len+1)
			a[np].fa=q;//don't write 'a[p].fa=q'!
		else{
			int nq=++tot;
			a[nq]=a[q];
			a[nq].len=a[p].len+1;//don't forget! 
			a[q].fa=a[np].fa=nq;
			for(;p&&a[p].c[x]==q;p=a[p].fa)
				a[p].c[x]=nq;
		}
	}
	siz[np]=1;
}

一、统计子串出现次数

一个子串的出现次数为它在母树中的儿子的数量,在母树上 \(dfs\) 即可。

例题:P3804 【模板】后缀自动机(SAM)

\(code:\)

	for(int i=0;i<s.size();++i)
		build(s[i]-'a');
	for(int i=1;i<=tot;++i)
		++c[a[i].len];
	for(int i=1;i<=tot;++i)
		c[i]+=c[i-1];
	for(int i=1;i<=tot;++i)
		id[c[a[i].len]--]=i;
	for(int i=tot;i>=1;--i){
		int p=id[i];
		siz[a[p].fa]+=siz[p];
		if(siz[p]>1)
			ans=max(ans,1ll*siz[p]*a[p].len);
	}
	printf("%lld\n",ans);
	return 0;

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

\(code:\)

void work(){
	tot=las=1;ans=0;
	cin>>s;scanf("%d",&n);
	for(int i=0;i<s.size();++i)
		build(s[i]-'a');
	for(int i=1;i<=tot;++i)
		++c[a[i].len];
	for(int i=1;i<=tot;++i)
		c[i]+=c[i-1];
	for(int i=1;i<=tot;++i)
		id[c[a[i].len]--]=i;
	for(int i=tot;i>=1;--i){
		int p=id[i];
		siz[a[p].fa]+=siz[p];
		if(siz[p]==n)//差分思想,令f[i]表示出现次数为n,长度为i的字符串个数,则sum[i]=f[i]-f[i+1] 
			++sum[a[p].len],--sum[a[a[p].fa].len];
	}
	for(int i=s.size();i>=1;--i){
		sum[i]+=sum[i+1];//得到上述的f[i]
		if(sum[ans]<sum[i])
			ans=i;
	}
	if(ans)
		printf("%d\n",ans);
	else
		printf("-1\n"); 
	for(int i=0;i<=tot;++i){
		c[i]=sum[i]=0;
		siz[i]=id[i]=a[i].fa=a[i].len=0;
		for(int j=0;j<26;++j)
			a[i].c[j]=0;
	}
}

二、统计不同子串个数

后缀自动机有一个性质:从根节点开始跑,每一条路径代表一个子串。

又因为后缀自动机是个 \(DAG\) ,所以在后缀自动机上跑 \(DP\) 即可。

例题:P2408 不同子串个数

\(code:\)

signed main(){
    scanf("%lld",&n);
	cin>>s;
	len=s.size();
	for(int i=0;i<len;++i)
		add(s[i]-'a');
	for(int i=1;i<=tot;++i)
		++cnt[a[i].len];
	for(int i=1;i<=len;++i)
		cnt[i]+=cnt[i-1];
	for(int i=1;i<=tot;++i)
		d[cnt[a[i].len]--]=i;
	for(int i=tot;i>=1;--i)
		siz[a[d[i]].fa]+=siz[d[i]];
	for(int i=1;i<=tot;++i)
		sum[i]=siz[i]=1;
	sum[1]=siz[1]=0;
	for(int i=tot;i>=1;--i)
		for(int j=0;j<26;++j)
			sum[d[i]]+=sum[a[d[i]].ch[j]];
	printf("%lld\n",sum[1]);
	return 0;
}

三、字典序第 \(K\) 小子串

例题:P3975 [TJOI2015] 弦论

令 \(siz[i]\) 表示 \(i\) 所代表的 \(Endpos\) 的集合大小,也就是 \(i\) 所对应字符串集合的出现次数

\(T=0\) 时,本质相同的子串在不同位置出现算相同,所以 \(siz[i]=1\) ,即将每个字符串集合的 \(Endpos\) 集合大小(字符串集合元素出现次数)置为1

\(T=1\) 时,本质相同的子串在不同位置出现算不同,那么累加后的 \(siz\) 表示实际上 \(Endpos\) 的集合大小

void dfs(int p,int k){
   if(k<=siz[p])
   	return ;
   k-=siz[p];
   for(int i=0;i<26;++i){
   	int to=a[p].ch[i];
   	if(!to)
   		continue;
   	if(k>sum[to])
   		k-=sum[to];
   	else{
   		printf("%c",i+'a'),dfs(to,k);
   		return ;
   	}
   }
}
int main(){
   cin>>s;
   scanf("%d%d",&t,&k);
   len=s.size();
   for(int i=0;i<len;++i)
   	add(s[i]-'a');
   for(int i=1;i<=tot;++i)
   	++cnt[a[i].len];
   for(int i=1;i<=len;++i)
   	cnt[i]+=cnt[i-1];
   for(int i=1;i<=tot;++i)
   	d[cnt[a[i].len]--]=i;
   for(int i=tot;i>=1;--i)
   	siz[a[d[i]].fa]+=siz[d[i]];
   for(int i=1;i<=tot;++i)
   	if(t==0)
   		sum[i]=siz[i]=1;
   	else
   		sum[i]=siz[i];
   sum[1]=siz[1]=0;
   for(int i=tot;i>=1;--i)
   	for(int j=0;j<26;++j)
   		sum[d[i]]+=sum[a[d[i]].ch[j]];
   if(sum[1]>=k)
   	dfs(1,k);
   else
   	printf("-1\n"); 
   return 0;
}

标签:fa,后缀,siz,sum,len,int,应用,--,自动机
From: https://www.cnblogs.com/andyl/p/17592062.html

相关文章

  • 【Spring Boot 初识丨八 丨外部应用程序属性 】
    上一篇讲了SpringBoot的外部化配置的加载顺序及一些简单的属性说明本篇来讲一讲外部化配置一些比较重要的部分SpringBoot初识:(外部化配置详解)外部应用程序属性  当您的应用程序启动时,SpringBoot将自动从以下位置查找并加载application.properties和application.......
  • Linux 系统安全及应用
    1.账号安全基本措施1.1系统账号清理将用户设置为无法登录、锁定账户删除账户锁定账户密码本质锁定使用userdel锁定用户userdel  用户名   只删除账户,不删除家目录文件夹userdel    -r   用户名   账户,家目录文件夹一起删除1.2锁定用......
  • 找回windows应用商店
    应用windows自带的应用商店,安装软件时,发现应用商店没了,则可以通过下面的方法找回1、在windows10 搜索  WindowsPowershell2、以管理员权限打开3、直接把下面这个语句粘贴进去Get-AppXPackage*WindowsStore*-AllUsers|Foreach{Add-AppxPackage-DisableDevelopme......
  • python数据分析师入门-学习笔记(第四节 爬虫的应用场景)
    学习链接:Python数据分析师入门实际应用企业中: 竞品调研数据采集 办公自动化个人: 比如看小说 有的网站收费 有的网站不收费,但是有广告 目标:不看广告不交钱 广告屏蔽插件 爬下来 比如说抢票、抢茅台、抢票.........
  • 智能视频分析技术烟火检测在视频监控场景中的应用
    智能视频分析技术烟火检测在视频监控场景中的应用随着炎夏到来,气温不断升高,生产、生活中一些细节稍不留意,就容易引发火灾、酿成灾害。夏季引发火灾事故主要包括电气火灾、汽车火灾、施工现场火灾、危化品火灾、物质自燃火灾、液化石油气火灾、电瓶车火灾、违章动火作业火灾等。根据......
  • Delphi轻松读写NDEF文本、智能海报、应用控制等NFC标签
        NDEF全称NFCdataexchangeformat即nfc数据交换格式,是一种标准化的数据格式,可用于在任何兼容的NFC设备与另一个NFC设备或标签之间交换信息。数据格式由NDEF消息和NDEF记录组成。    NDEF信息可以写到不同类型的NFC芯片中,如NFC_Forum_Type2类的Ntag2x、FM1......
  • VS选择Visual C++中的控制台项目和空项目、Windows桌面应用程序三者之间有什么区别?
    在VisualStudio中创建C/C++项目时,可以选择控制台项目、空项目和Windows桌面应用程序,它们有以下区别:控制台项目(ConsoleApplication):这种项目类型适用于命令行应用程序的开发。它提供一个命令行界面,可以在控制台中进行输入和输出操作,通常用于简单的控制台程序,如计算器、文件......
  • 22-Hive函数应用
    1.多字节分隔符1.1问题与需求【默认规则】Hive默认序列化类是LazySimpleSerDe,其只支持使用单字节分隔符(char)来加载文本数据,例如逗号、制表符、空格等等,默认的分隔符为”\001”。根据不同文件的不同分隔符,我们可以通过在创建表时使用rowformatdelimited来指定文件中的分......
  • 为什么使用 CDN 需要 Angular 应用正确返回 HTTP 200 和 404 状态码
    CDN(ContentDeliveryNetwork)是内容分发网络,它的目的是通过在各地建立节点缓存数据,使用户可以就近获取数据,从而提高数据获取的速度和稳定性。Angular是一种用于构建客户端应用的开发平台。它带来了一种新的方式来构建应用,完全是在浏览器中运行,无需借助任何后端服务。HTTP200......
  • TypeScript 对象解构操作符在 Spartacus 实际项目开发中的应用
    下面这段代码来自Spartacus项目的navigation-entry-item.reducer.ts实现。import{NodeItem}from'../../model/node-item.model';import{CmsActions}from'../actions/index';exportconstinitialState:NodeItem|undefined=undefined;exportfu......