Pagini recente » Cod sursa (job #773771) | Cod sursa (job #1601221) | Cod sursa (job #2810621) | Cod sursa (job #170661) | Cod sursa (job #2515425)
#include <bits/stdc++.h>
#define DIMM 1000010
#define DIM_CUV 10010
#define DIM 110
using namespace std;
FILE *fin = fopen ("ahocorasick.in","r");
FILE *fout = fopen ("ahocorasick.out","w");
struct trie{
trie *f[26];
trie *back; /// nodul care se duce in sus
vector <trie*> v;
int cnt;
trie(){
back = 0;
cnt = 0;
for (int i=0;i<26;++i)
f[i] = 0;
}
};
trie *rad = new trie;
trie *sol[DIM];
char v[DIMM],s[DIM_CUV];
int n,m,i,j;
deque <trie*> c;
void add_trie (trie *rad, char *s){
if (*s == 0){
/// inseamna ca am ajuns la final
sol[i] = rad;
return;
}
if (!rad->f[*s-'a']) /// trb sa adaug litera
rad->f[*s-'a'] = new trie;
add_trie (rad->f[*s-'a'],s+1); /// tec la urmatoarea litera
}
void dfs (trie *nod){
for (int i=0;i<nod->v.size();++i){
dfs (nod->v[i]);
nod->cnt += nod->v[i]->cnt;
}
}
int main (){
fscanf (fin,"%s\n",v+1); /// sirul mare
/// construiesc trie ul cu toate cuvintele
fscanf (fin,"%d\n",&n);
for (i=1;i<=n;++i){
fscanf (fin,"%s\n",s);
add_trie (rad,s);
}
/// acum trebuie sa fac bfs pe trie ca sa determin acele muchii de intoarcere
c.push_back(rad);
while (!c.empty()){
trie *nod = (trie *)c.front();
c.pop_front();
for (i=0;i<=25;++i){
if (!nod->f[i])
continue;
/// ma duc in sus cat timp nu dau de litera care imi trebuie
trie *aux = nod->back;
while (aux != NULL && aux->f[i] == NULL)
aux = aux->back;
if (aux == NULL){ /// nu am gasit nimic, deci leg de radacina
nod->f[i]->back = rad;
} else nod->f[i]->back = aux->f[i];
nod->f[i]->back->v.push_back(nod->f[i]);
c.push_back(nod->f[i]);
}}
/// acum trb sa parcurg sirul principal
m = strlen (v+1);
trie *nod = rad;
for (i=1;i<=m;++i){
int val = v[i] - 'a';
while (nod != rad && nod->f[val] == NULL)
nod = nod->back;
if (nod->f[val] != NULL){
nod = nod->f[val];
++nod->cnt;
}
}
/// dfs din radacina pt sume partiale
dfs (rad);
for (i=1;i<=n;++i)
fprintf(fout,"%d\n",sol[i]->cnt);
return 0;
}