Pagini recente » Cod sursa (job #1568545) | Cod sursa (job #1063148) | Cod sursa (job #41244) | Cod sursa (job #278534) | Cod sursa (job #2830068)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
const int LGCUV = 10005;
const int NMAX = 1000005;
char a[NMAX],cuv[LGCUV];
int n;
struct Trie{
int cnt;
Trie *fiu[26],*back;
vector<Trie*> v;
Trie(){
cnt=0;
for(int i=0;i<26;i++)
fiu[i]=NULL;
back=NULL;
v.clear();
}
};
Trie *rasp[105];
Trie v[NMAX];
int cnt_trie=0;
Trie *root = v+(cnt_trie++);
Trie *update(Trie *node,char *ch){
if(*ch==0) return node;
if(node->fiu[*ch-'a']==NULL)
node->fiu[*ch-'a']= v+(cnt_trie++);
return update(node->fiu[*ch-'a'],ch+1);
}
void bfs(){
queue <Trie*> q;
q.push(root);
while(!q.empty()){
Trie *node = q.front();
q.pop();
for(int i=0;i<26;i++){
if(node->fiu[i]==NULL) continue;
Trie *b = node->back;
while(b!=NULL and b->fiu[i]==NULL) b=b->back;
if(b==NULL) b=root;
else b=b->fiu[i];
node->fiu[i]->back = b;
b->v.push_back(node->fiu[i]);
q.push(node->fiu[i]);
}
}
}
void dfs(Trie *node){
vector<Trie*>::iterator i;
for(i=node->v.begin();i!=node->v.end();i++){
dfs(*i);
node->cnt+=(*i)->cnt;
}
}
int main()
{
fin >> a;
fin >> n;
for(int i=1;i<=n;i++){
fin >> cuv;
rasp[i]=update(root,cuv);
}
bfs();
Trie *nod = root;
for(char *ch=a;*ch;ch++){
while(nod!=NULL and nod->fiu[*ch-'a']==NULL)
nod=nod->back;
if(nod==NULL) nod=root;
else nod=nod->fiu[*ch-'a'];
nod->cnt++;
}
dfs(root);
for(int i=1;i<=n;i++){
fout << rasp[i]->cnt << '\n';
}
return 0;
}