CF163E. e-Government AC自动机+fail树+分块-程序员宅基地

技术标签: CF  分块  AC自动机  

原题:http://codeforces.com/contest/163/problem/E

题解:给k个字符串,维护3种操作,添加一个字符串,删除一个字符串,查询模式串在主串中出现了几次。暴力来做,跑ac自动机,统计所有的失败指针对应的字符串。考虑如何优化,将失败指针反向,那么模式串的子树就是答案。用深搜序转换成线性,再用对应的数据结构维护就可以,可以用线段树,树状数组,数列分块等。我用的数列分块。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e6+10;
const int M=1e3+10;
const int Z=26;
struct E{int x,y,next;}mm[N];
int ch[N][Z],nxt[N],h[N],l[N],r[N],a[N],sum[M],pos[N];
int tot,n,k,cnt,num,m,end1[N];
bool vis[N],v[N];
char s[N];
inline void ins(char *s,int ind){
	int len=strlen(s+1);int p=1;
	for(int i=1;i<=len;i++){
		int c=s[i]-'a';
		if(!ch[p][c]) ch[p][c]=++tot;
		p=ch[p][c];
	}
	end1[ind]=p;
}
void bfs(){
	queue<int> q;
	for(int i=0;i<Z;i++) ch[0][i]=1;
	nxt[1]=0;q.push(1);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=0;i<Z;i++)
			if(!ch[u][i]) ch[u][i]=ch[nxt[u]][i];
			else {
				q.push(ch[u][i]);int v;
				for(v=nxt[u];v>0 && !ch[v][i];v=nxt[v]);
				nxt[ch[u][i]]=ch[v][i];
			}	
	}
}
inline void insE(int x,int y){
	mm[++cnt].x=x;mm[cnt].y=y;mm[cnt].next=h[x];h[x]=cnt;
}
void dfs(int u){
	l[u]=++num;vis[u]=1;
	for(int k=h[u];k;k=mm[k].next){
		int v=mm[k].y;if(!vis[v]) dfs(v);
	}
	r[u]=num;
}
void add(int l,int r,int c){
	for(int i=l;i<=min(r,pos[l]*m);i++) a[i]+=c;
	if(pos[l] != pos[r]){
		for(int i=(pos[r]-1)*m+1;i<=r;i++) a[i]+=c;
	}
	for(int i=pos[l]+1;i<=pos[r]-1;i++) sum[i]+=c;
}
inline int query(int x){return a[x]+sum[pos[x]];}
int main(){
//	freopen("cf163e.in","r",stdin);
	tot=1;memset(h,0,sizeof h);num=0;cnt=0;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=k;i++) scanf("%s",s+1),ins(s,i);
	bfs();
	for(int i=2;i<=tot;i++) insE(nxt[i],i);
	dfs(1);
	m=sqrt(num);
	for(int i=1;i<=num;i++) pos[i]=(i-1)/m+1;
	for(int i=1;i<=k;i++) add(l[end1[i]],r[end1[i]],1),v[i]=1;	
	while(n--){
		scanf("%s",s);int len=strlen(s)-1;
		if( s[0]== '+' ){
			int x=0;
			for(int j=1;j<=len;j++) x=(x<<1)+(x<<3)+s[j]-'0';
			if(!v[x])add(l[end1[x]],r[end1[x]],1),v[x]=1;
		}
		
		if( s[0]== '-' ){
			int x=0;
			for(int j=1;j<=len;j++) x=(x<<1)+(x<<3)+s[j]-'0';
			if(v[x])add(l[end1[x]], r[end1[x]],-1),v[x]=0;
		}
		if( s[0]== '?' ){
			int p=1;int ans=0;
			for(int i=1;i<=len;i++){
				int c=s[i]-'a';int k=ch[p][c];
				p=ch[p][c];
				ans+=query(l[k]);
			}
			printf("%d\n",ans);	 
		}
	}
	return 0;
}

 

 

 

 

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_39689721/article/details/87022560

智能推荐

喜大普奔:新可美购物广场终于迎来开业季_商场试营业文章-程序员宅基地

文章浏览阅读149次。随着服务回龙观地区及周边居民20年的京客隆撤离该地区便民服务措施锐减给周边居民带来了生活上很大的不便经历过短暂的痛苦后终于迎来了新的希望回龙观地区居民福利来了真来了这次是真的来了二拨子桥东,G6(原八达岭高速)辅路旁新可美购物广场终于揭开诱人的面纱面向回龙观地区及周边居民敞开双臂热拥您的到来2021年9月29日新可美购物广场开业仪式将在广场前侧盛大举行同时也揭开了新可美购物广场9月29日——10月7日为期9天的开业季5000份礼品等着您_商场试营业文章

为什么不能在字符串上使用switch语句?_java中字符串为什么不能用switchcase-程序员宅基地

文章浏览阅读994次。此功能是否将在以后的Java版本中使用? 有人可以解释为什么我不能这样做吗,例如Java的switch语句的技术方式? _java中字符串为什么不能用switchcase

获取某年某月的第一天是星期几-程序员宅基地

文章浏览阅读6.7k次。首先我们要知道是哪一年那一个月:例如2018年6月代码:var nowdate=new Date('2018,06,01');var weekday=nowdate.getDay()这样获取到的weekday有可能是0/1/2/3/4/5/6,要注意返回是0代表这个月的第一天是星期天,其他的依次类推就可以知道是这个月的第一天是星期几了。当然一般我们实战时候不可能写死年月,所以要var year=2..._某年某月的第一天是星期几

安卓videoView 横屏,全屏显示_android 自定义view 可全屏 全屏时是横屏-程序员宅基地

文章浏览阅读5.8k次,点赞5次,收藏8次。 videoView的原码中对videoView播放的视频做了一定的处理导致视频不能按你以为的形式呈现在videoView中。首先重写VideoView &lt;RelativeLayout android:layout_width="match_parent" android:layout_height="match_parent"..._android 自定义view 可全屏 全屏时是横屏

Linux系统启动Oracle数据库报错问题集锦_the specified adr base directory does not exist [/-程序员宅基地

文章浏览阅读6.1k次,点赞4次,收藏21次。1、报错:could not open parameter file '/data/oracle/product/11.2.0/db_1/dbs/initorcl.ora'[oracle@localhost ~]$ sqlplus /nologSQL*Plus: Release 11.2.0.1.0 Production on Mon Dec 17 17:19:08 2018Copyr..._the specified adr base directory does not exist [/data/oracle/product/11.2.0

【Python自学笔记】多任务,多线程,threading模块的使用_threading mysql-程序员宅基地

文章浏览阅读143次。文章目录并行&并发threading模块Thread类(线程)查看线程数量线程执行代码的封装多线程-全局变量并行&并发CPU的核心数 >= 任务数量,称之为并行任务数量 > CPU核心数,称之为并行并行是真的多任务,并发是“假的多任务”threading模块Thread类(线程)启动线程_示例import threadingimport t..._threading mysql

随便推点

消费向上商业向下,爱特茂商业奥莱MALL项目入驻山东,引领商业项目空前发展_潍坊新辰里购物中心-程序员宅基地

文章浏览阅读292次。  素称“齐鲁大地”,儒家文化发源地的山东省,是我国人口大省之一,常住人口10152.7万人。提起山东,人们最先想到的会是青岛、济南这些经济与旅游业都极为发达的城市,但山东最具有潜力的城市却不是这些,而是正在奋起直追的潍坊。  2016年潍坊便被认定为“中国最具投资潜力和发展活力的新兴经济强市”之一,2021年全市实现生产总值7010.6亿元,同比增长9.7%,全市社会消费品零售总额实现2781.5亿元,同比增长16.4%,按消费类型分,商品零售2589.1亿元,增长15.5%;餐饮收入192.4亿元,增_潍坊新辰里购物中心

理解SpringMVC核心原理和设计模式应用背景_springmvc 的这种 mvc 模式了解吗?他的工作原理是什么?用到了哪些设计模式?-程序员宅基地

文章浏览阅读511次。对Java程序员来讲,做web开发最熟悉的框架莫过于SpringMVC了。之所以它能一统江湖,不是自己太优秀,而是对手太坑了,不知道大家还记不记得2017年左右Struts2爆出了一个大漏洞,自此之后,Web开发领域的就是SpringMVC的天下了。但是鉴于这么优秀的框架,很多程序员还只是停留在会用的状态,对底层的原理却不甚了解,所以今天咱么就来聊聊SpringMVC的工作原理。三层架构在开始介绍SpringMVC之前,咱么要先来了解一下web开发的历史。我们的开发架构一般都是..._springmvc 的这种 mvc 模式了解吗?他的工作原理是什么?用到了哪些设计模式?

Kali渗透Windows Server 2003_kali渗透run报错-程序员宅基地

文章浏览阅读7.8k次,点赞6次,收藏29次。两台虚拟机kali ip 192.168.18.128windows ip 192.168.18.1331)首先先扫描一下靶机nmap -sS -sV -O -Pn 192.168.18.133其中sS是半开放扫描,sV是扫描版本号,O是扫描操作系统,Pn是不进行ping,会快一点。可以看到有445端口,且是windows server 2003。2)使用msfco..._kali渗透run报错

Oracle Database Configuration Assistant 打不开-程序员宅基地

文章浏览阅读2.8k次。1:如果想要创建新的数据库实例,你一定熟悉的 DataBase Configuration Assistant ,但出现以下标志。 如下方式也是解决问题的一种。 2:解决方式(1)找到oracle安装目录bin文件下的dbca.bat,双击,如图所示: (2)选中“下一步”点击,如下图所示就可以创建新的数据库实例了。 ..._database configuration assistant打不开

go 项目的规范_go 项目设计准则-程序员宅基地

文章浏览阅读249次。本文档为个人博客文档系统的备份版本、作者:小游、作者博客:点击访问发现一个不错的开源库https://github.com/golang-standards/project-layout解释https://wjp2013.github.io/go/go-project-structure/参考文章:1.https://studygolang.com/articles/122592.https://github.com/whjstc/openbilibili-go-common-1/tree._go 项目设计准则

定义Person类,Person类中含有两个属性name 和age ,使用compare方法比较两个对象是否为同一个对象。假定name 和age 都相同就似为同一个对象_定义一个person类,包括name和age两个属性-程序员宅基地

文章浏览阅读1.6w次。/*思路:1.用private定义String类型的name,和int类型的age2.定义boolean类型的函数compare,利用if来判断name和age是否相同。3.如果相同就返回true,否则返回false*/class Person{private String name;//private 权限修饰符private int age;Pe_定义一个person类,包括name和age两个属性

推荐文章

热门文章

相关标签