Pagini recente » Cod sursa (job #3228920) | Cod sursa (job #3169128) | Cod sursa (job #1751928) | Cod sursa (job #36482) | Cod sursa (job #1581984)
#include <stdio.h>
#include <queue>
#include <vector>
#include <string.h>
#define chr(x) (x - 'a')
using namespace std;
const int Ml = 1e6 + 7;
const int Mx = 1e4 + 5;
const int Mn = 1e2 + 3;
struct trie
{
int cnt;
trie *next[26],*fail;
vector< trie* > vec;
trie()
{
cnt = 0;
fail = 0;
memset(next,0,sizeof(next));
}
};
int n,id;
char a[Ml],b[Mx];
queue< trie* > q;
trie *word[Mn],*root = new trie();
void add(trie *node,char *p)
{
if (*p == 0)
{
word[id] = node;
return;
}
if (node->next[chr(*p)] == 0)
node->next[chr(*p)] = new trie();
add(node->next[chr(*p)],p + 1);
}
void dfs(trie *node)
{
for (auto aux : node->vec)
{
dfs(aux);
node->cnt += aux->cnt;
}
}
int main()
{
freopen("ahocorasick.in","r",stdin);
freopen("ahocorasick.out","w",stdout);
scanf("%s\n%d",a,&n);
int m = strlen(a);
for (int i = 1;i <= n;i++)
{
scanf("%s\n",b);
id = i;
add(root,b);
}
q.push(root);
while (!q.empty())
{
trie *node = q.front();
q.pop();
for (int i = 0;i < 26;i++)
if (node->next[i])
{
trie *aux = node->fail;
while (aux != 0 && aux->next[i] == 0)
aux = aux->fail;
if (aux == 0)
{
node->next[i]->fail = root;
root->vec.push_back(node->next[i]);
}
else
{
node->next[i]->fail = aux->next[i];
aux->next[i]->vec.push_back(node->next[i]);
}
q.push(node->next[i]);
}
}
trie *aux = root;
for (int i = 0;i < m;i++)
{
while (aux != 0 && aux->next[chr(a[i])] == 0)
aux = aux->fail;
if (aux == 0)
aux = root;
else
aux = aux->next[chr(a[i])];
aux->cnt++;
}
dfs(root);
for (int i = 1;i <= n;i++)
printf("%d\n",word[i]->cnt);
return 0;
}