由于論文的需要，看了一下AC自動(dòng)機(jī)的原理，感覺(jué)就是trie樹+kmp，這兩個(gè)單獨(dú)都寫過(guò)，
但是合在一起還真沒(méi)寫過(guò)，參照網(wǎng)上的代碼寫了一個(gè)HDU上的題目，水的很，入門級(jí)別的。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 500005
#define KIND 26
struct node
{
node *fail;
node *next[KIND];
int count;
node()
{
fail = NULL;
count = 0;
memset(next, 0, sizeof(next));
}
}*queue[N];
void insert(node *root, char *str)
{
int i = 0, index;
node *p = root;
while(str[i])
{
index = str[i] - 'a';
if(p->next[index] == NULL) p->next[index] = new node();
p = p->next[index];
i++;
}
p->count++;
}
void build(node *root)
{
int front = 0, rear = 0;
root->fail = NULL;
queue[rear++] = root;
while(front < rear)
{
node *tmp = queue[front++];
node *p = NULL;
for(int i = 0; i < KIND; i++)
{
if(tmp->next[i])
{
p = tmp->fail;
while(p)
{
if(p->next[i])
{
tmp->next[i]->fail = p->next[i];
break;
}
p = p->fail;
}
if(!p) tmp->next[i]->fail = root;
queue[rear++] = tmp->next[i];
}
}
}
}
char str[1000005];
int query(node *root)
{
int i = 0, ans = 0, index;
node *p = root, *tmp;
while(str[i])
{
index = str[i] - 'a';
while(p->next[index] == NULL && p != root) p = p->fail;
p = p->next[index];
if(!p) p = root;
tmp = p;
while(tmp != root)
{
ans += tmp->count;
tmp->count = 0;
tmp = tmp->fail;
}
i++;
}
return ans;
}
int main()
{
int t, nkey, ans;
char key[100];
scanf("%d", &t);
while(t--)
{
node *root = new node();
scanf("%d", &nkey);
for(int i = 0; i < nkey; i++)
{
scanf("%s", key);
insert(root, key);
}
build(root);
scanf("%s", str);
ans = query(root);
printf("%d\n", ans);
}
return 0;
}