Pagini recente » Cod sursa (job #2960092) | Cod sursa (job #2614979) | Cod sursa (job #2110993) | Cod sursa (job #1941187) | Cod sursa (job #2808099)
#include <bits/stdc++.h>
#define n_max 100000
using namespace std;
ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");
char sentence[10000001], w[10001];
int result[10001];
int st, fin, n;
struct trie{
int number;
vector<int> indices;
trie *children['z' - 'a' + 1], *fail;
trie()
{
number = 0;
memset(children, 0, sizeof(children));
fail = NULL;
}
};
trie *T = new trie, *U = new trie;
trie *q[10000 * 10000 + 5];
void insert(trie *node, char *s, int index)
{
if(!isalpha(*s))
{
node -> indices.push_back(index);
return;
}
int next = *s - 'a';
if(!(node -> children[next]))
node -> children[next] = new trie;
insert(node -> children[next], s + 1, index);
}
void read()
{
f>>sentence;
f>>n;
for(int i = 1;i <= n;++i)
f>>w, insert(T, w, i);
}
void compose()
{
trie *fa, *top;
T -> fail = T;
for(q[st = fin = 1] = T;st <= fin;++st)
{
top = q[st];
for(int ch = 0;ch < 'z' - 'a' + 1;++ch)
if(top -> children[ch])
{
for(fa = top -> fail;fa != T && !fa -> children[ch];fa = fa -> fail);
if(fa -> children[ch] && fa -> children[ch] != top -> children[ch]) fa = fa -> children[ch];
top -> children[ch] -> fail = fa;
q[++fin] = top -> children[ch];
}
}
}
void calculate()
{
trie *top;
for(int i = fin;i >= 1;--i)
{
top = q[i];
if(top -> fail) top -> fail -> number += top -> number;
for(auto it : top -> indices)
result[it] += top -> number;
}
}
void solve()
{
compose();
U = T;
for(int i = 0;i < strlen(sentence);++i)
{
int next = sentence[i] - 'a';
while(U != T && !U -> children[next]) U = U -> fail;
if(U -> children[next])
U = U -> children[next];
U -> number++;
}
calculate();
for(int i = 1;i <= n;++i)
g<<result[i]<<'\n';
}
int main()
{
read();
solve();
return 0;
}