HDoj 3065 acオートマチック
比較的裸のacオートマチックです
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
struct cnode
{
char STR[52];
int ans;
}node[1010];
struct trie
{
trie* next;
int isend;
int map;// root ,trie , node
trie* child[26];
trie()
{
isend = 0;
map = 0;
memset(child,NULL,sizeof(child));
next = NULL;
}
}*root,Tnum[160000];
int cnt;
void insert(char* str,int INDEX)
{
int num;
int len;
trie* ptr;
ptr = root;
int i;
len = strlen(str);
for(i = 0;i < len;i++)
{
num = str[i] - 'A';
if(ptr->child[num] == NULL)
{
ptr->child[num] = &Tnum[++cnt];// new
}
ptr = ptr->child[num];
}
ptr -> isend ++;
/* if(ptr->isend>1)
{
cout<<"yes"<<endl;
}*/
ptr->map = INDEX;
}
void ac_automation()
{
int i;
queue<trie*> qu;
trie* current=NULL;
qu.push(root);
trie* fail = NULL;
while(!qu.empty())
{
current = qu.front();
qu.pop();
for(i = 0;i < 26;i++)
{
if(current->child[i] != NULL)
{
fail =current->next;
if(current == root)
{
current->child[i]->next = root;
qu.push(current->child[i]);
continue;
}
while(1)
{
if(fail == NULL)
{
current->child[i]->next = root;
break;
}
else
{
if(fail->child[i] != NULL)
{
current->child[i]->next = fail->child[i];
break;
}
}
fail = fail->next;
}
qu.push(current->child[i]);
}
}
}
}
char text[2000010];
int ans;
void query()
{
int len;
len=strlen(text);
trie* ptr;
ptr = root;
int num;
int i;
trie* temp;
for(i = 0;i<len;i++)
{
if(text[i]>='A'&&text[i]<='Z')
{
num = text[i]-'A';
}
else
{
ptr = root;
continue;
}
while(ptr->child[num] ==NULL && ptr!=root)
{
ptr = ptr->next;
}
ptr = ptr->child[num];
if(ptr == NULL)
{
ptr = root;
}
temp = ptr;
while(temp!=root &&temp->isend !=-1)
{
node[temp->map].ans+=temp->isend;
// temp->isend = -1;
temp = temp->next;
}
}
}
int main()
{
int n;
int i;
char str[52];
while(scanf("%d",&n)!=EOF)
{
memset(Tnum,NULL,sizeof(Tnum));
root = &Tnum[0];// new
cnt=0;
for(i=0;i<n;i++)
{
scanf("%s",node[i].STR);
node[i].ans =0;
insert(node[i].STR,i);
}
getchar();
ac_automation();
// scanf("%s",text);
gets(text);
query();
for(i=0;i<n;i++)
{
if(node[i].ans != 0)
{
printf("%s: %d
",node[i].STR,node[i].ans);
}
}
}
return 0;
}