#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <vector>
using namespace std;
struct Trie
{
int cnt;
Trie* next[52], *prefix;
}Table[1000000];
int idx,id;
Trie* root;
char str[1000011];
bool visite[1010];
vector<int> flag[1010];
void init(){
idx= 0; id= 1;
root= &Table[idx];
memset( Table[0].next, 0, sizeof(Table[0].next) );
Table[0].cnt= 0; Table[0].prefix= NULL;
memset( visite, false, sizeof(visite) );
}
void insert( char* s )
{
Trie* r= root;
while( *s ){
int t;
if( *s>= 'a' && *s<= 'z' )t= *s- 'a';
if( *s>= 'A' && *s<= 'Z' )t= *s- 'A'+ 26;
if( !r->next[t] ){
++idx;
memset( Table[idx].next, 0, sizeof(Table[idx].next) );
Table[idx].cnt= 0; Table[idx].prefix= NULL;
r->next[t]= &Table[idx];
}
r= r->next[t]; s++;
}
if( r->cnt ) flag[r->cnt].push_back( id++ );
else r->cnt= id++;
}
void get_prefix()
{
Trie* r= root;
queue<Trie*> q;
q.push( root ); root->prefix= NULL;
while( !q.empty() ){
Trie* father= q.front(); q.pop();
for( int i= 0; i< 52; ++i )
if( father->next[i] ){
Trie* tmp= father->prefix;
while( tmp && !tmp->next[i] ) tmp= tmp->prefix;
if( !tmp ) father->next[i]->prefix= root;
else father->next[i]->prefix= tmp->next[i];
q.push( father->next[i] );
}
}
}
void ac_run(){
Trie* p= root;
char* s= str;
while( *s ){
int t;
if( *s>= 'a' && *s<= 'z' )t= *s- 'a';
if( *s>= 'A' && *s<= 'Z' )t= *s- 'A'+ 26;
while( !p->next[t] && p!= root ) p= p->prefix;
p= p->next[t];
if( !p ) p= root;
Trie* tp= p;
while( tp!= root && tp->cnt!= 0 ){
visite[tp->cnt]= true;
tp= tp->prefix;}
s++;
}
}
int main()
{
int test, n;
char s[1010];
scanf("%d",&test); getchar();
while( test-- ){
gets(str); init();
scanf("%d",&n ); getchar();
for( int i= 0; i< n; ++i ) {
gets(s); insert(s); }
get_prefix(); ac_run();
for( int i= 1; i<= n; ++i )
if( visite[i] ){
for( size_t j= 0; j< flag[i].size(); ++j )
visite[ flag[i][j] ]= true;}
for( int i=1; i<=n;++i)
if(visite[i])puts("y");
else puts("n");
for(int i= 0; i<= n; ++i ) flag[i].clear();
}
return 0;
}
posted on 2009-04-15 15:42
Darren 阅读(524)
评论(0) 编辑 收藏 引用