Pagini recente » Cod sursa (job #766746) | Profil MihneaGhira | Cod sursa (job #1130198) | Cod sursa (job #360937) | Cod sursa (job #1093080)
#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;
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 cp(trie &r, int ver, int lit, trie *lastp) {
if(ver)
r.pref = &rad;
else {
while(lastp != &rad && !lastp->f[lit])
lastp = lastp->pref;
r.pref = lastp->f[lit];
}
for(int i = 0; i < 26; ++i)
if(r.f[i])
cp(*r.f[i], 0, i, r.pref);
}
void calcpref() {
int i;
for(i = 0; i < S; ++i) if(rad.f[i])
cp(*rad.f[i], 1, i, 0);
}
void df(trie &r) {
int i;
for(i = 0; i < S; ++i) if(r.f[i]) {
df(*r.f[i]);
r.nr += r.f[i]->nr;
}
for(vector<int>::iterator it = r.cuv.begin(); it != r.cuv.end(); ++it)
rez[*it] = r.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';
bool ver = 1;
while(pozc != &rad && !pozc->f[a[i]]) {
pozc = pozc->pref;
pozc->nr++;
ver = 0;
}
if(ver)
pozc->nr--;
pozc = pozc->f[a[i]];
pozc->nr++;
}
while(pozc != &rad) {
pozc = pozc->pref;
pozc->nr++;
}
df(rad);
for(i = 1; i <= n; ++i)
cout << rez[i] << "\n";
return 0;
}