Educational Codeforces Round 16 F - String Set Queries (CDQ分治+AC自动机)
hdu 5421 Victor and String (支持双向添加的回文树)

2017 ACM/ICPC 南宁 D Banned Patterns

zjhl2 posted @ 2018年9月19日 02:37 in with tags AC自动机 , 1122 阅读

题目链接:

https://nanti.jisuanke.com/t/19970

 

思路:

KMP做这道题的想法
模板ABCA变成 -1 -1 -1 3
询问CBAABCA变成 -1 -1 -1 1 3 5 3(记作diff)
 
next数组是 0  1  2 3
匹配CBAABCA的时候,我记f[i]为匹配到第i个字符时候,模板串最长能匹配到哪,模板串匹配的最长位置为j
这样f就是  1 2 3 1 2 3 4
 
为什么f[4]变成了1,因为匹配到第四个的时候,要求s[4]==s[4-1],j一直跳到1,这时候diff[4]>=next,意味着这个diff[4]已经没用了,要变成-1
 
这样diff就变成了 -1 -1 -1 -1 3 5 3,此时j指向1
 
然后求f[5],发现5-3>=j,就把3变成-1,来匹配,因为让s[5]==s[2]已经没有用了,模板串长度不够,不需要考虑这个3
 
这样diff又变成了-1 -1 -1 -1 -1 5 3,此时next匹配上了,变成2
 
一直下去,求出所有的f

 

复杂度不会算,因为询问串每次都跳fail,不知道会覆盖多少个不同的状态,最坏情况是可能会是len^2?

 

#include<bits/stdc++.h>
using namespace std;

const int N=100005;

int fail[N],cnt[N],deep[N];
map<int,int>ch[N];
int tot,root;
int newnode(){
	tot++;
	ch[tot].clear();
	fail[tot]=0;  cnt[tot]=0;
	return tot;
}
void init(){
	for (int i=0;i<=tot;i++) ch[i].clear();
	root=newnode();
}
void insert(int *s,int n){
	int now=root;
	int _deep=0;
	for (int i=1;i<=n;i++){
		_deep++;
		int w=s[i];
		assert(w<_deep);
		if (!ch[now].count(w)) ch[now][w]=newnode();
		now=ch[now][w];
		deep[now]=_deep;
	}
	cnt[now]++;
}
int getnext(int u,int w){
	if (w>=deep[u]+1) w=-1;
	// for (auto &p:ch[u]){
	// 	printf("ch %d:%d %d\n",u,p.first,p.second);
	// }
	// printf("%d %d %d \n",u,w,ch[u].count(w));
	while(u!=root&&!ch[u].count(w)){
		u=fail[u];
		if (w>=deep[u]+1) w=-1;
	}
	if (ch[u].count(w)) return ch[u][w];
	return u;
}
void build(){
	queue<int>Q;
	fail[root]=root;
	for (auto &p:ch[root]){
		int v=p.second;
		fail[v]=root;
		Q.push(v);
	}
	while(!Q.empty()){
		int u=Q.front(); Q.pop();
		for (auto &p:ch[u]){
			int v=p.second;
			fail[v]=getnext(fail[u],p.first);
			Q.push(v);
		}
	}
}
int T;
int vis[N];
bool query(int *s,int n){
	int now=root;
	for (int i=1;i<=n;i++){
		int w=s[i];
		now=getnext(now,w);
		for (int v=now;v!=root&&vis[v]!=T;v=fail[v]){
			vis[v]=T;
			if (cnt[v]) return 1;
		}
	}
	return 0;
}

char s[N*10];
int a[N*10];
int pre[26];
int main(){
	int t; scanf("%d",&t);
	for (int cas=1;cas<=t;cas++){
		init();
		int n; scanf("%d",&n);
		for (int i=1;i<=n;i++){
			memset(pre,0,sizeof(pre));
			scanf("%s",s+1);
			int m=0;
			for (int j=1;s[j];j++){
				int w=s[j]-'A';
				if (pre[w]) a[j]=j-pre[w];
				else a[j]=-1;
				pre[w]=j;
				m++;
				// printf("%d ",a[j]);
			}
			insert(a,m);
		}
		build();
		// for (int i=1;i<=tot;i++) printf("%d %d %d\n",i,fail[i],deep[i]);
		scanf("%d",&n);
		printf("Case #%d: ",cas);
		for (int i=1;i<=n;i++){
			T++;
			memset(pre,0,sizeof(pre));
			scanf("%s",s+1);
			int m=0;
			for (int j=1;s[j];j++){
				int w=s[j]-'A';
				if (pre[w]) a[j]=j-pre[w];
				else a[j]=-1;
				pre[w]=j;
				m++;
			}
			if (query(a,m)) printf("Y");
			else printf("N");
			if (i==n) printf("\n");
			else printf(" ");
		}

	}
}

 

Avatar_small
CGBSE Model Paper Cl 说:
2022年9月05日 00:18

CG Board Model Paper 2023 Class 9 Pdf Download with Answers for English Medium, Hindi Medium, Urdu Medium & Students for Small Answers, Long Answer, Very Long Answer Questions, and Essay Type Questions to Term1 & Term2 Exams at official website. CGBSE Model Paper Class 9 New Exam Scheme or Question Pattern for Sammittive Assignment Exams (SA1 & SA2): Very Long Answer (VLA), Long Answer (LA), Small Answer (SA), Very Small Answer (VSA), Single Answer, Multiple Choice and etc.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter