2017 ACM/ICPC 南宁 D Banned Patterns

题目链接：

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

思路：

复杂度不会算，因为询问串每次都跳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(" ");
		}

	}
}