Pagini recente » Cod sursa (job #2834359) | Cod sursa (job #2282997) | Cod sursa (job #2467196) | Cod sursa (job #1500751) | Cod sursa (job #1100741)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <memory.h>
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
const int Nmax = 110;
const int Amax = 26;
const int Smax = 1e6 + 100;
const int Cmax = 1e4 + 100;
struct AC{
vector <int> End;
AC *F[Amax], *fail;
int nr;
AC()
{
fail = 0; nr = 0;
memset(F, 0, sizeof F);
}
};
int N, st, dr, SOL[Nmax];
char A[Smax], C[Cmax];
AC *Q[Cmax * Cmax], *T;
void Insert(AC *nod, char *p, int i)
{
if(*p == NULL)
{
nod -> End.push_back(i);
return;
}
int next = *p - 'a';
if(!nod -> F[next]) nod -> F[next] = new AC;
Insert(nod -> F[next], p + 1, i);
}
void BFS()
{
T->fail = T;
AC *fpoz;
Q[1] = T;
for(st = dr = 1; st <= dr; st++)
{
AC *nod = Q[st];
for(int i = 0; i < Amax; i++)
if(nod->F[i] != NULL)
{
for(fpoz = nod->fail; fpoz != T && fpoz->F[i] == NULL; fpoz = fpoz->fail);
if(fpoz->F[i] != NULL & fpoz->F[i] != nod->F[i]) fpoz = fpoz->F[i];
nod->F[i]->fail = fpoz;
Q[++dr] = nod->F[i];
}
}
T->fail = NULL;
}
void REV_BFS()
{
for(; dr > 0; dr--)
{
AC *nod = Q[dr];
if(nod->fail != NULL)
nod->fail->nr += nod->nr;
for(int i = 0; i < nod->End.size(); i++)
SOL[nod->End[i]] = nod->nr;
}
}
int main()
{
fin.getline(A + 1, Smax);
fin >> N; T = new AC; fin.get();
for(int i = 1; i <= N; i++)
{
fin.getline(C + 1, Cmax);
Insert(T, C + 1, i);
}
BFS();
int M = strlen(A + 1); AC *nod = T;
for(int i = 1; i <= M; i++)
{
int next = A[i] - 'a';
for(; nod != T && nod->F[next] == NULL; nod = nod->fail);
if(nod->F[next] != NULL) nod = nod->F[next];
++nod->nr;
}
REV_BFS();
for(int i = 1; i <= N; i++)
fout << SOL[i] << '\n';
return 0;
}