记录编号	159194	评测结果	AAAAAAAAAAAAAAA
题目名称	审查	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.194 s
提交时间	2015-04-20 12:04:25	内存使用	17.19 MiB

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cctype>
#include <algorithm>
#include <cmath>
using namespace std;
//#define USEFREAD
#ifdef USEFREAD
#define InputLen 5000000
char *ptr=(char *)malloc(InputLen);
#define getc() (*(ptr++))
#else
#define getc() (getchar())
#endif
#define SetFile(x) (freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout))
template<class T>inline void getd(T &x){
    char ch = getc();bool neg = false;
    while(!isdigit(ch) && ch != '-')ch = getc();
    if(ch == '-')ch = getc(), neg = true;
    x = ch - '0';
    while(isdigit(ch = getc()))x = x * 10 - '0' + ch;
    if(neg)x = -x;
}
/***********************************************************************/
const int maxn = 1000005, Sig = 26, maxm = 100005;
struct Trie *Root = NULL;
struct Trie{
	Trie *son[Sig], *fail;
	int rec;
	inline Trie *trans(int ch){
		if(son[ch])return son[ch];
		return fail ? fail->trans(ch) : Root;
	}
}trie[maxm], *Pit = trie;

char T[maxn], S[maxm], *begin[maxm], ans[maxn], *Ait = ans;
int Scnt;

void insert(Trie *&cur, char *it, char *end, int id){
	if(cur == NULL)cur = Pit++;
	if(it == end){
		cur->rec = id;
		return;
	}
	insert(cur->son[*it - 'a'], it+1, end, id);
}
#include <queue>
inline void Build(){
	queue<Trie *> Q;
	Trie *t, **s;
	int i;
	for(i = 0,s = Root->son;i < Sig;++i,++s)if(*s){
		(*s)->fail = Root;
		Q.push(*s);
	}
	while(!Q.empty()){
		t = Q.front();Q.pop();
		for(i = 0,s = t->son;i < Sig;++i,++s){
			if(*s){
				(*s)->fail = t->fail->trans(i);
				Q.push(*s);
			}
			else *s = t->trans(i);
		}
	}
}

inline void init(){
	begin[1] = S;
	scanf("%s", T);
	getd(Scnt);
	int i;
	char *it;
	for(i = 1;i <= Scnt;++i){
		it = begin[i];
		while(!isalpha(*it = getc()));++it;
		while(isalpha(*it = getc()))++it;
		insert(Root, begin[i], begin[i+1] = it, i);
	}
	Build();
}

Trie *loc[maxn], **lit = loc;
inline void work(){
	Trie *t = Root;
	char *it = T;
	int tmp, d;
	*(lit++) = Root;
	while(*it){
		t = t->trans(*it - 'a');
		*(Ait++) = *it;
		*(lit++) = t;
		if((tmp = t->rec)){
			d = begin[tmp+1] - begin[tmp];
			Ait -= d;lit -= d;
			t = *(lit - 1);
		}
		++it;
	}
	*Ait = 0;
	printf("%s\n", ans);
}

int main(){
	#ifdef DEBUG
	freopen("test.txt", "r", stdin);
	#else       
	SetFile(censor);
	#endif
	#ifdef USEFREAD
	fread(ptr,1,InputLen,stdin);
	#endif
	
	init();
	work();
	
#ifdef DEBUG
    printf("\n%.3lf sec \n", (double)clock() / CLOCKS_PER_SEC);
#endif
    return 0;
}