Pagini recente » Cod sursa (job #2296633) | Cod sursa (job #1666299) | Cod sursa (job #1277354) | Cod sursa (job #897736) | Cod sursa (job #2721949)
#include <bits/stdc++.h>
using namespace std;
ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");
char s[1000005], cuv[10005];
int n, st, sf, rez[100];
struct trie
{
int nr;
vector<int> ter;
trie *fiu[26], *fail;
trie()
{
nr = 0;
memset(fiu, 0, sizeof(fiu));
fail = NULL;
}
};
trie *T = new trie, *U = new trie;
trie *q[100 * 100000 + 5];
void insert(trie *nod, char *s, int index)
{
if(!(*s))
{
nod -> ter.push_back(index);
return;
}
int urm = *s - 'a'
if(!(nod -> fiu[urm]))
nod -> fiu[urm] = new trie;
insert(nod -> fiu[urm], s + 1, index);
}
void Read()
{
f>>s;
f>>n;
for(int i = 1;i <= n;++i)
f>>cuv, insert(T, cuv, i);
}
void compute()
{
trie *top, *fa;
T -> fail = T;
for(q[st = sf = 1] = T;st <= sf;++st)
{
top = q[st];
for(short ch = 0;ch < 26;++ch)
if(top -> fiu[ch])
{
for(fa = top -> fail;fa != T && !fa -> fiu[ch];fa = fa -> fail);
if(fa -> fiu[ch] && fa -> fiu[ch] != top -> fiu[ch]) fa = fa -> fiu[ch];
top -> fiu[ch] -> fail = fa;
q[++sf] = top -> fiu[ch];
}
}
}
void reverse()
{
trie *top;
for(int i = sf;i > 0;--i)
{
top = q[i];
if(top -> fail) top -> fail -> nr += top -> nr;
for(auto it : top -> ter)
rez[it] += top -> nr;
}
}
void Solve()
{
compute();
U = T;
for(int i = 0;i < strlen(s);++i)
{
int urm = s[i] - 'a';
for(;U != T && !U -> fiu[urm];U = U -> fail);
if(U -> fiu[urm]) U = U -> fiu[urm];
U -> nr++;
}
reverse();
for(int i = 1;i <= n;++i)
g<<rez[i]<<'\n';
}
int main()
{
Read();
Solve();
return 0;
}