记录编号	252143	评测结果	AAAAAAAAAA
题目名称	情书	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	1.734 s
提交时间	2016-04-19 16:19:34	内存使用	24.67 MiB

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<map>
using namespace std;
const int maxn = 1e5;

int n;

class ac_m {
private:
	bool app[105];
	int fail[maxn];
	int ns[maxn][27]; 
	int node_cnt;
	int last[maxn];
	int end[maxn];
public:
	void insert(char *a, int num) {
		int now = 0;
		for(int i = 1; a[i]; i++) {
			if(!ns[now][a[i]-'a'+1]) ns[now][a[i]-'a'+1] = ++node_cnt;
			now = ns[now][a[i]-'a'+1];
			if(!a[i+1]) end[now] = num;
		}
	}
	
	void build() {
		queue<int> q;
		for(int i = 1; i <= 27; i++) if(ns[0][i]) q.push(ns[0][i]);
		while(!q.empty()) {
			int now = q.front(); q.pop();
			for(int i = 1; i <= 27; i++) {
				int son = ns[now][i];
				if(!son) continue;
				q.push(son); 
				int f = fail[now];
				while(f && !ns[f][i]) f = fail[f];
				fail[son] = ns[f][i];
				last[son] = end[ fail[son] ] ? fail[son] : last[ fail[son] ];
			}
		}
	}
	
	void check(int now) {
		if(now) {
			app[end[now]] = true;
			check(last[now]);
		}
	}
	
	bool query(char *a) {
		memset(app, 0, sizeof(app));
		int now = 0;
		for(int i = 1; a[i]; i++) {
			while(now && !ns[now][a[i]-'a'+1]) now = fail[now];
			now = ns[now][a[i]-'a'+1];
			if(end[now]) check(now);
			else check(last[now]);
		}
		for(int i = 1; i <= n; i++) {
			if(app[i]) continue;
			return false;
		}
		return true;
	}
	
}ac;

char q[105][105];
char la[maxn*200];

bool get_line(char *a) {
	int i = 0;
	char tmp = getchar();
	while((tmp < 'a' || tmp > 'z') && (tmp < 'A' || tmp > 'Z')) {
		if(tmp == EOF) return false;
		tmp = getchar();
	}
	while(tmp != '$') {
		a[++i] = tmp;
		tmp = getchar();
	}
	a[++i] = '\0';
	return true;
}

void read() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%s", q[i]+1);
		ac.insert(q[i], i);
	}
}

void solve() {
	ac.build();
	while(get_line(la)) {
		if(ac.query(la)) printf("Yes\n");
		else printf("No\n");
	}
}

int main() {
	freopen("lettera.in", "r", stdin);
	freopen("lettera.out", "w", stdout);
	read();
	solve();
	return 0;
}