Pagini recente » Cod sursa (job #838188) | Cod sursa (job #770033) | Cod sursa (job #2955345) | Cod sursa (job #1982312) | Cod sursa (job #2188286)
#include <bits/stdc++.h>
using namespace std;
struct trie{
trie *f[26], *fail;
vector<int> v;
int occ;
trie(){
occ = 0;
fail = NULL;
memset(f, 0, sizeof(f));
}
};
const string fisier = "ahocorasick";
char r[1000005], c[10005];
int n, sol[105], szr, szc;
trie *rad = new trie;
int main()
{
ifstream fin (fisier+".in");
ofstream fout (fisier+".out");
fin >> r >> n;
szr = strlen(r);
for (int i = 1; i <= n; ++i){
fin >> c;
szc = strlen(c);
trie *t = rad;
for (unsigned j = 0; j < szc; ++j){
int q = c[j]-'a';
if(t->f[q] == NULL)
t->f[q] = new trie;
t = t->f[q];
}
t->v.push_back(i);
}
int vf = -1;
vector<trie*> qu;
qu.push_back(rad);
rad->fail = rad;
while(vf != qu.size()-1){
trie *t = qu[++vf];
for (int i = 0; i < 26; ++i)
if(t->f[i]){
trie *fail = t->fail;
while(fail != rad && fail->f[i] == NULL)
fail = fail->fail;
if(fail->f[i] != NULL && fail->f[i] != t->f[i])
fail = fail->f[i];
t->f[i]->fail = fail;
qu.push_back(t->f[i]);
}
}
rad->fail = NULL;
trie *t = rad;
for (unsigned i = 0; i < szr; ++i){
int q = r[i]-'a';
while(t != rad && t->f[q] == NULL)
t = t->fail;
if(t->f[q] != NULL)
t = t->f[q];
++t->occ;
}
for (int i = vf; i >= 0; --i){
t = qu[i];
if(t->fail != NULL)
t->fail->occ += t->occ;
for (vector<int>::iterator it = t->v.begin(); it != t->v.end(); ++it)
sol[*it] = t->occ;
}
for (int i = 1; i <= n; ++i)
fout << sol[i] << "\n";
return 0;
}