AC自动机再试。
CODE:
/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2010-6-12
DESCRIPTION:
UVa10679
*/
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
#include <string>
using std::string;
#include <list>
using std::list;
#include <string.h>
#define H(c) (((c)<=’z’&&(c)>=’a’)?((c)-‘a’):((c)-‘A’+’z’-‘a’+1))
#define NEXT_SIZE (‘z’-‘a’+1)+(‘Z’-‘A’+1)
#define NODE_SIZE 1000000
#define QUEUE_SIZE 1000000
#define CHECK_SIZE 1000000
#define NEW 1
#define DELETE 2
struct node
{
node* fail;
node* next[NEXT_SIZE];
bool end;
};
node* who[CHECK_SIZE];
node* get(int flag=0)
{
static node* pool;
static int top;
if (!flag)
{
memset(pool+top,0,sizeof(node));
return pool+top++;
}
else
{
switch (flag)
{
case NEW:
pool=new node[NODE_SIZE];
top=0;
break;
case DELETE:
delete[] pool;
break;
}
return 0;
}
}
void insert(node* const root,const char* str,int id)
{
node* p=root;
do
{
if (!p->next[H(*str)]) p->next[H(*str)]=get();
p=p->next[H(*str)];
}
while (*(++str));
who[id]=p;
}
void build_ac_automation(node* const root)
{
static node* q[QUEUE_SIZE];
node** head;
node** tail;
*(head=tail=q)=root;
while (head<=tail)
{
node* qh=*(head++);
for (char i=’a’;i<=’z’;i++)
if (qh->next[H(i)])
{
if (qh==root) qh->next[H(i)]->fail=root;
else
{
node* p=qh->fail;
while (p)
{
if (p->next[H(i)])
{
qh->next[H(i)]->fail=p->next[H(i)];
break;
}
p=p->fail;
}
if (!p) qh->next[H(i)]->fail=root;
}
*(++tail)=qh->next[H(i)];
}
for (char i=’A’;i<=’Z’;i++)
if (qh->next[H(i)])
{
if (qh==root) qh->next[H(i)]->fail=root;
else
{
node* p=qh->fail;
while (p)
{
if (p->next[H(i)])
{
qh->next[H(i)]->fail=p->next[H(i)];
break;
}
p=p->fail;
}
if (!p) qh->next[H(i)]->fail=root;
}
*(++tail)=qh->next[H(i)];
}
}
}
void query(node* const root,const char* str)
{
int result=0;
node* p=root;
do
{
while (!p->next[H(*str)]&&p!=root) p=p->fail;
p=p->next[H(*str)];
if (!p) p=root;
node* t=p;
while (t!=root)
{
t->end=true;
t=t->fail;
}
}
while (*(++str));
}
class Application
{
int CASE,N;
string keywords;
string description;
public:
Application()
{
std::ios::sync_with_stdio(false);
cin>>CASE;
}
int run()
{
for (int i=0;i<CASE;i++)
{
cin>>description;
cin>>N;
get(NEW);
node* root=get();
for (int j=1;j<=N;j++)
{
cin>>keywords;
insert(root,keywords.c_str(),j);
}
build_ac_automation(root);
query(root,description.c_str());
for (int j=1;j<=N;j++)
cout<<char(who[j]->end?’y’:’n’)<<endl;
get(DELETE);
}
return 0;
}
};
int main()
{
Application app;
return app.run();
}