Pagini recente » Cod sursa (job #530971) | Cod sursa (job #2982915) | Cod sursa (job #2757478) | Cod sursa (job #971086) | Cod sursa (job #2302678)
#include <bits/stdc++.h>
#define LA 1000001
#define LB 10001
#define ch c[k]-'a'
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
string s, c;
int n, st, dr, ans[105];
struct Trie{
int n0;
vector <int> ind;
Trie *fii[26], *fail;
Trie(){
n0 = 0;
fail = NULL;
memset(fii, NULL, sizeof(fii));
}
};
Trie *T, *q[LB];
void Insert(Trie *nod, int k, int poz)
{
if(c[k] == '\0')
{
nod->ind.push_back(poz);
return;
}
int next = c[k]-'a';
if(nod->fii[next] == NULL) nod->fii[next] = new Trie;
Insert(nod->fii[next], k+1, poz);
}
void BFS(Trie *t)
{
st = dr = 1;
t->fail = t;
for(q[st] = t; st <= dr; st++)
{
Trie *f = q[st];
for(int i = 0; i < 26; i++)
{
if(f->fii[i] == NULL)
continue;
Trie *d;
for(d = f->fail; d->fii[i] == NULL && d!=t; d = d->fail);
if(d->fii[i] != NULL && d->fii[i] != f->fii[i]) d = d->fii[i];
f->fii[i]->fail = d;
q[++dr] = f->fii[i];
}
}
t->fail = NULL;
}
void BFT(Trie *t)
{
Trie *f;
for(int i = dr; i >0; i--)
{
f = q[i];
if(f->fail != NULL) f->fail->n0 += f->n0;
for(int j = 0; j < f->ind.size(); j++)
ans[f->ind[j]] = f->n0;
}
}
int main()
{
fin >> s;
fin >> n;
T = new Trie;
Trie *g;
for(int i = 1; i <= n; i++)
{
fin >> c;
Insert(T, 0, i);
}
BFS(T);
g = T;
for(int i = 0; i < s.size(); i++)
{
int next = s[i] - 'a';
for(; g->fii[next] == NULL && g != T; g = g->fail);
if(g->fii[next] != NULL) g = g->fii[next];
g->n0++;
}
BFT(T);
for(int i = 1; i <= n; i++)
fout << ans[i] << '\n';
return 0;
}