首页 > 其他分享 >伟大的 chy,请赐予我力量&chy 自动机的 SAM 做法

伟大的 chy,请赐予我力量&chy 自动机的 SAM 做法

时间:2022-11-10 19:23:56浏览次数:72  
标签:pre ch 前缀 SAM int len fa chy 自动机

https://www.luogu.com.cn/problem/U260001

给定一组文本串,再每次给你一个询问串,求文本串的前缀集合中有多少串的 border 集合包含该询问串。

考虑 border 也许会往 kmp 方面入手,因为 kmp 能求出来一个前缀的最长 border。但注意到,这个包含意味着可能不是最长的,而不是最长的你对应位置又要发生变化,显然无法从最长 border 转移。

然而,你观察到一个串的 border 集合包含询问串,显然询问串是该串的前缀,且该串又作为后缀出现。

于是考虑对每个文本串的前缀求出其 endpos,其 endpos 位置的前缀的 border 集合一定包含该询问前缀。

至于去重,你考虑用 trie 对于出现过的前缀就不赋值,但询问的时候还是要考虑其贡献的。

对答案的记录直接挂在 trie 上即可。

#include <bits/stdc++.h>
//#define int long long
#define pb push_back
using namespace std;
const int N=(int)(5e6+5);
struct edge {
	int nex,to;
}e[N*3];
char s[N];
bool fl[N];
int las,tot=1,m,q,n,val[N*3],len[N*3],fa[N*3],cch[26][N],ctot=1,ch[26][N],sz[N*3],hea[N*3],cnt;

void add_edge(int x,int y) {
	e[++cnt].nex=hea[x]; e[cnt].to=y; hea[x]=cnt;
}

//int ins(int pre,int c,bool ok) {
//	if(ch[c][pre]&&len[ch[c][pre]]==len[pre]+1) return ch[c][pre];
//	int x=++tot; bool chk=ch[c][pre]; len[x]=len[pre]+1; 
//	if(ok) sz[x]=1;
//	for(;pre&&!ch[c][pre];pre=fa[pre]) ch[c][pre]=x;
//	int y=ch[c][pre];
//	if(!pre) {
//		fa[x]=1; return x;
//	} else if(len[y]==len[pre]+1) {
//		fa[x]=y; return x;
//	}
//	int p=++tot; len[p]=len[pre]+1;
//	fa[p]=fa[y]; fa[x]=fa[y]=p;
//	for(int i=0;i<26;i++) ch[i][p]=ch[i][y];
//	for(;pre&&ch[c][pre]==y;pre=fa[pre]) ch[c][pre]=p;
//	if(chk) return p;
//	return x;
//}

void ins(int c,bool ok) {
	int x=++tot,pre=las; las=x; len[x]=len[pre]+1;
	sz[x]=ok;
	for(;pre&&!ch[c][pre];pre=fa[pre]) ch[c][pre]=x;
	int y=ch[c][pre];
	if(!pre) return fa[x]=1,void();
	else if(len[y]==len[pre]+1) return fa[x]=y,void();
	else {
		int p=++tot; len[p]=len[pre]+1;
		fa[p]=fa[y]; fa[y]=fa[x]=p;
		for(int i=0;i<26;i++) ch[i][p]=ch[i][y];
		for(;pre&&ch[c][pre]==y;pre=fa[pre]) ch[c][pre]=p;
	} 
}

void dfs(int x) {
//	cout<<x<<" "<<sz[x]<<'\n';
	for(int i=hea[x];i;i=e[i].nex) {
		int y=e[i].to;
		dfs(y); sz[x]+=sz[y];
	}
}

signed main() {
	cin.tie(0); ios::sync_with_stdio(false);
	cin>>m>>q;
	while(m--) {
		cin>>s+1; n=strlen(s+1);
		las=tot=1; int p=1;
		for(int i=1;i<=n;i++) {
			bool ok=0; int c=s[i]-'a';
			if(!cch[c][p]) cch[c][p]=++ctot,ok=1;
			p=cch[c][p];
			ins(c,ok);
//			las=ins(las,s[i]-'a',ok);
			fl[i]=ok;
		}
		for(int i=2;i<=tot;i++) add_edge(fa[i],i);
		dfs(1);
		int tp=1; p=1;
		for(int i=1;i<=n;i++) {
			int c=s[i]-'a';
			tp=cch[c][tp]; p=ch[c][p];
			if(fl[i]) {
				if(sz[p]>=1) val[tp]+=sz[p]-1;
			} else {
				if(sz[p]) val[tp]+=sz[p];
			}
		}
		for(int i=1;i<=n;i++) fl[i]=0;
		for(int i=1;i<=tot;i++) {
			sz[i]=hea[i]=fa[i]=len[i]=0;
			for(int j=0;j<26;j++) ch[j][i]=0;
		}
		cnt=0; las=1; tot=1;
	}
	while(q--) {
		cin>>s+1; n=strlen(s+1);
		int p=1; bool ok=1;
		for(int i=1;i<=n;i++) {
			int c=s[i]-'a';
			if(!cch[c][p]) {
				ok=0; break ;
			}
			p=cch[c][p];
		}
		if(!ok) {
			cout<<"0\n"; continue ;
		}
		cout<<val[p]<<'\n';
	}
	return 0;
} 

标签:pre,ch,前缀,SAM,int,len,fa,chy,自动机
From: https://www.cnblogs.com/xugangfan/p/16878105.html

相关文章

  • MySQL的InnerDB和MySAM索引实现
     InnoDB索引实现 InnoDB也使用B+Tree作为索引结构,但具体实现方式却与MyISAM截然不同。InnoDB的主索引:MyISAM索引文件和数据文件是分离的,索引文件仅保......
  • 预告|AutoML Meetup V1 第四范式 & 百度 & AWS ,共探自动机器学习最佳实践
    自动机器学习(AutoML)是将机器学习应用于现实问题的端到端流程自动化的过程。随着机器学习部署场景的增多和机器学习算法的进步,AutoML的应用得到了进一步的发展。作为降低AI......
  • 究竟什么是软件资产管理(SAM)?企业应该怎么做?
    软件资产管理通俗意义是指在国际上流行的一种清晰明确和可执行的管理计划,是一种科学的管理方法,是一系列帮助企业充分利用软件资产和应用程序的总和。软件资产管理是一个有机......
  • 回文自动机PAM从菜到菜
    回文自动机基础操作两个初始状态一个长度为\(0,-1\)的偶回文根和奇回文根。转移\(\delta(x,c)\)从\(x\)节点代表的回文串转移到两端加入字符\(c\)后到达的节点......
  • windows-classic-samples
    windows-classic-samples-github一个例子今天查找PostQueuedCompletionStatus的官方例子,就在github发现了这个宝库下载后,发现里面有很多官方给出的范例,按照英文......
  • innodb引擎,myisam引擎,memory引擎区别【最新版】
    innodb引擎.frm表结构文件.idb数据和索引文件innodb引擎执行count(*)的时候,需要把数据一行一行地从引擎里面读出来,累积计数事务型数据库首选,支持事务ACID支持行......
  • AC自动机
    \(tr[i].end\)为\(1\)时表示为该节点为串尾。\(tr[i].sum\)表示以该点为串尾的字符串数。普通自动机P3121[USACO15FEB]CensoringG考虑对模式串建出自动机,在串尾......
  • ubuntu samba 配置
    1.说明samba配置主要分为安装samba、配置samba、添加用户等步骤。2.安装sambasudoapt-getinstallsambasudoapt-getinstallsmbclient3.配置samba打开配置文件sudo......
  • CHY 自动机
    \(\text{CHY}\)自动机『这个不是直接\(\text{AC}\)自动机吗?』『怎么\(\text{AC}\)自动机?』『搞棵\(\text{Trie}\)出来,然后在上面挂指针,拿节点去做数位\(\text......
  • pve proxmox 挂载新目录 samba SMB CIFS 报错
    PVE后台storage添加SMB/CIFS类型的storage报错,例如mounterror:Refertothemount.cifs(8)manualpage(e.g.manmount.cifs)andkernellogmessages(dmesg)......