Pagini recente » Cod sursa (job #3196599) | Cod sursa (job #3034911) | Cod sursa (job #2055248) | Cod sursa (job #941727) | Cod sursa (job #1568403)
#include<fstream>
#include<vector>
#include<cstring>
#include<deque>
using namespace std;
int n, i, m;
char a[1000005], s[10005];
struct trie{
int nr;
trie *v[26];
trie *back;
vector<trie*> w;
trie(){
nr = 0;
w.clear();
back = NULL;
for(int i = 0; i < 26; i++){
v[i] = NULL;
}
}
};
trie *p, *f[105], *nod, *aux;
deque<trie*> c;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
trie *adauga(char *s, trie *r){
if(*s == 0){
return r;
}
else{
if(r->v[*s - 'a'] == NULL){
r->v[*s - 'a'] = new trie;
}
return adauga(s + 1, r->v[*s - 'a']);
}
}
void dfs(trie *nod){
for(int i = 0; i < nod->w.size(); i++){
dfs(nod->w[i]);
nod->nr += nod->w[i]->nr;
}
}
int main(){
p = new trie;
fin>> a;
fin>> n;
for(i = 1; i <= n; i++){
fin>> s;
f[i] = adauga(s, p);
}
c.push_back(p);
while(!c.empty()){
nod = c.front();
c.pop_front();
for(i = 0; i < 26; i++){
if(nod->v[i] != NULL){
aux = nod->back;
while(aux != NULL && aux->v[i] == NULL){
aux = aux->back;
}
if(aux == 0){
nod->v[i]->back = p;
}
else{
nod->v[i]->back = aux->v[i];
}
nod->v[i]->back->w.push_back(nod->v[i]);
c.push_back(nod->v[i]);
}
}
}
m = strlen(a);
aux = p;
for(i = 0; i < m; i++){
while(aux != NULL && aux->v[a[i] - 'a'] == NULL){
aux = aux->back;
}
if(aux == NULL){
aux = p;
}
else{
aux->v[a[i] - 'a']->nr++;
aux = aux->v[a[i] - 'a'];
}
}
dfs(p);
for(i = 1; i <= n; i++){
fout<< f[i]->nr <<"\n";
}
return 0;
}