Pagini recente » Cod sursa (job #2502185) | Cod sursa (job #718906) | Cod sursa (job #3140028) | Cod sursa (job #830005) | Cod sursa (job #1546314)
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
#define MAX 1000010
char a[MAX], b[10010];
int st, dr, rez[102];
struct trie{
int indice = 0;
int nr = 0;
trie *fiu[26] = {0}, *fail = 0;
} *T, *Q[MAX];
void introdu(trie *nod, char c[], int ind)
{
if(c[0] == 0)
{
nod->indice = ind;
return;
}
if(nod->fiu[c[0] - 'a'] == 0)
{
nod->fiu[c[0] - 'a'] = new trie;
}
introdu(nod->fiu[c[0] - 'a'], c + 1, ind);
}
int main()
{
int n, i;
T = new trie;
fin >> a;
fin >> n;
for(i = 1 ; i <= n ; i++)
{
fin >> b;
introdu(T, b, i);
}
st = dr = 0;
Q[st] = T;
T->fail = T;
while(st <= dr)
{
trie *nod = Q[st];
st++;
for(i = 0 ; i < 26 ; i++)
{
if(nod->fiu[i])
{
Q[++dr] = nod->fiu[i];
trie *son = nod->fiu[i];
son->fail = nod->fail;
while(son != T && son->fail->fiu[i] == 0)
son->fail = son->fail->fail;
if(son->fail->fiu[i] && son->fail->fiu[i] != son)
son->fail = son->fail->fiu[i];
}
}
}
trie *nod = T;
for(i = 0 ; a[i] ; i++)
{
while(nod != T && nod->fiu[a[i] - 'a'] == 0)
nod = nod->fail;
if(nod->fiu[a[i] - 'a'])
nod = nod->fiu[a[i] - 'a'];
nod->nr++;
}
for(i = dr ; i >= 1 ; i--)
{
Q[i]->fail->nr += Q[i]->nr;
rez[Q[i]->indice] = Q[i]->nr;
}
for(i = 1 ; i <= n ; i++)
{
fout << rez[i] << "\n";
}
}