Pagini recente » Cod sursa (job #885504) | Cod sursa (job #792038) | Cod sursa (job #1550758) | Cod sursa (job #1850299) | Cod sursa (job #1093162)
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
const int A = 1100000;
const int B = 11000;
const int N = 105;
const int S = 26;
struct trie {
vector<int> cuv;
trie *f[S], *pref;
int nr;
trie() {
nr = 0;
pref = 0;
for(int i = 0; i < S; ++i)
f[i] = 0;
}
};
char a[A], b[B];
int n, rez[N], pc, nn, ns = 1;
trie *ord[N * B];
trie rad;
void add(trie &r, int poz) {
if(!b[poz]) {
r.cuv.push_back(pc);
return;
}
if(!r.f[b[poz] - 'a'])
r.f[b[poz] - 'a'] = new trie;
add(*r.f[b[poz] - 'a'], poz + 1);
}
void calcpref() {
int i;
ord[++nn] = &rad;
rad.pref = &rad;
trie *pr;
while(nn >= ns) {
trie *el = ord[ns++];
for(i = 0; i < S; ++i) if(el->f[i]) {
ord[++nn] = el->f[i];
pr = el->pref;
while(pr != &rad && !pr->f[i])
pr = pr->pref;
pr = pr->f[i];
if(!pr)
pr = &rad;
el->f[i]->pref = pr;
if(el->f[i] == pr)
el->f[i]->pref = &rad;
}
}
}
void bf(trie &r) {
int i;
for(i = nn; i; --i) {
if(ord[i]->pref)
ord[i]->pref->nr += ord[i]->nr;
for(vector<int>::iterator it = ord[i]->cuv.begin(); it != ord[i]->cuv.end(); ++it)
rez[*it] = ord[i]->nr;
}
}
int main() {
int i;
freopen("ahocorasick.in", "r", stdin);
freopen("ahocorasick.out", "w", stdout);
cin.getline(a, A);
cin >> n;
cin.get();
for(i = 1; i <= n; ++i) {
pc = i;
cin.getline(b, B);
add(rad, 0);
}
calcpref();
trie *pozc = &rad;
for(i = 0; a[i]; ++i){
a[i] -= 'a';
while(pozc && pozc != &rad && !pozc->f[a[i]])
pozc = pozc->pref;
if(!pozc)
continue;
pozc = pozc->f[a[i]];
if(!pozc)
pozc = &rad;
pozc->nr++;
}
bf(rad);
for(i = 1; i <= n; ++i)
cout << rez[i] << "\n";
return 0;
}