比赛 20160419s 评测结果 AAAAAAAAAA
题目名称 情书 最终得分 100
用户昵称 KZNS 运行时间 1.434 s
代码语言 C++ 内存使用 1.23 MiB
提交时间 2016-04-19 10:54:10
显示代码纯文本
//KZNS
#include <fstream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
//
ifstream fin ("lettera.in");
ofstream fout ("lettera.out");
class poi {
public:
	int nt[26], fail, t;
	poi() {
		t = false;
		memset(nt, 0, sizeof(nt));
	}
}tr[10003];
//
int N;
int tru = 1;
bool ined[103];
int sm;
//
inline int cid(char c) {
	if (c >= 'a')
		return c - 'a';
	else
		return c - 'A';
}
inline void mkac() {
	fin >> N;
	string s;
	int t;
	for (int i = 1; i <= N; i++) {
		fin >> s;
		t = 0;
		for (int j = 0; j < s.length(); j++) {
			if (tr[t].nt[cid(s[j])])
				t = tr[t].nt[cid(s[j])];
			else {
				tr[t].nt[cid(s[j])] = tru;
				t = tru++;
			}
		}
		if (tr[t].t) {
			i--;
			N--;
		}
		else
			tr[t].t = i;
	}
	queue<int> ls;
	tr[0].fail = -1;
	int u, v;
	for (int i = 0; i < 26; i++) {
		if (tr[0].nt[i]) {
			ls.push(tr[0].nt[i]);
			tr[tr[0].nt[i]].fail = 0;
		}
	}
	while (!ls.empty()) {
		u = ls.front();
		ls.pop();
		for (int i = 0; i < 26; i++) {
			if (tr[u].nt[i]) {
				v = tr[u].nt[i];
				ls.push(v);
				t = tr[u].fail;
				while (t >= 0) {
					if (tr[t].nt[i]) {
						tr[v].fail = tr[t].nt[i];
						break;
					}
					else {
						t = tr[t].fail;
					}
				}
				if (t < 0) {
					tr[v].fail = 0;
				}
			}
		}
	}
}
inline void dlt(int t) {
	while (t > 0) {
		ined[tr[t].t] = true;
		t = tr[t].fail;
	}
}
inline bool work() {
	char c;
	if (!(fin >> c))
		return false;
	memset(ined, 0, sizeof(ined));
	int t = 0;
	while (c!='$') {
		if (t < 0) {
			t = 0;
			fin >> c;
		}
		else if (tr[t].nt[cid(c)]) {
			t = tr[t].nt[cid(c)];
			fin >> c;
			dlt(t);
		}
		else {
			t = tr[t].fail;
		}
	}
	for (int i = 1; i <= N; i++) {
		if (!ined[i]) {
			fout << "No" << endl;
			return true;
		}
	}
	fout << "Yes" << endl;
	return true;
}
//
int main() {
	mkac();
	while (work());
	return 0;
}
//UBWH