題目大意:給出一組單詞,和一個文本,要你統計有多少個單詞出現在這個文本中。
解題思路:簡單的AC自動機入門,先把單詞建立單詞樹,注意單詞有重複出現,然後建構失敗指針。
最後用文本在自動機上做查詢統計個數
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int maxn = 55;
const int maxm = 1000010;
const int kind = 26;
struct node
{
node *fail;
node *next[kind];
int isLeaf;
node()
{
fail = NULL;
isLeaf = 0;
memset(next, 0, sizeof(next));
}
};
int t, n;
char str[maxn], text[maxm];
void insert(char *s, node *root);
void build(node *root);
int query(char *s, node *root);
int main()
{
scanf("%d", &t);
while(t-- != 0)
{
scanf("%d", &n);
node *root = new node;
for(int i = 0; i < n; i++)
{
scanf("%s", str);
insert(str, root);
}
build(root);
scanf("%s", text);
printf("%d\n", query(text, root));
}
return 0;
}
void insert(char *s, node *root)
{
int i = 0, index;
node *p = root;
while(s[i] != '\0')
{
index = s[i] - 'a';
if(!p->next[index])
p->next[index] = new node();
p = p->next[index];
i++;
}
p->isLeaf++;
}
void build(node *root)
{
node *tmp , *p;
queue<node *> que;
root->fail = NULL;
que.push(root);
while(!que.empty())
{
tmp = que.front();
p = NULL;
que.pop();
for(int i = 0; i < kind; i++)
{
if(tmp->next[i] != NULL)
{
if(tmp == root)
tmp->next[i]->fail = root;
else
{
p = tmp->fail;
while(p != NULL)
{
if(p->next[i] != NULL)
{
tmp->next[i]->fail = p->next[i];
break;
}
p = p->fail;
}
if(p == NULL)
tmp->next[i]->fail = root;
}
que.push(tmp->next[i]);
}
}
}
}
int query(char *s, node *root)
{
int ans = 0, i = 0, index;
node *p = root, *tmp = NULL;
while(s[i] != '\0')
{
index = s[i] - 'a';
while(p != NULL && p->next[index] == NULL)
p = p->fail;
if(p == NULL)
p = root;
else
p = p->next[index];
tmp = p;
while(tmp != NULL && tmp->isLeaf != 0)
{
ans += tmp->isLeaf;
tmp->isLeaf = 0;
tmp = tmp->fail;
}
i++;
}
return ans;
}