Pagini recente » Cod sursa (job #2196144) | Cod sursa (job #1345181) | Cod sursa (job #2105405) | Cod sursa (job #2021235) | Cod sursa (job #877637)
Cod sursa(job #877637)
#include <cstring>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("ahocorasick.in"); ofstream g("ahocorasick.out");
struct trie
{ int val;
trie *son[26], *next;
vector <trie *> V;
trie()
{ memset(son,0,sizeof(son));
val=0;
next=0;
}
};
trie *T=new trie;
trie *add(trie *now, char *chn)
{ if(*chn==0) return now;
if(now->son[*chn-'a']==0)
{ trie *aux=new trie;
now->son[*chn-'a']=aux;
}
now=now->son[*chn-'a'];
++chn;
return add(now, chn);
}
int N;
char A[1000002], B[102][10002];
queue<trie*> Q;
trie *where[102];
void Dfs(trie *now)
{ for (vector<trie*>::iterator it = now->V.begin(); it != now->V.end(); ++it)
{ Dfs(*it);
now->val += (*it)->val;
}
}
int main()
{ f>>A>>N;
for(int i=1; i<=N; ++i)
{ f>>B[i];
where[i]=add(T,B[i]);
}
Q.push(T);
while(!Q.empty())
{ trie *now=Q.front(); Q.pop();
for(int i=0; i<26; ++i)
if(now->son[i]!=0)
{ trie *aux=now->next;
while(aux && aux->son[i]==0) aux=aux->next;
if(aux)
{ now->son[i]->next=aux->son[i];
aux->son[i]->V.push_back(now->son[i]);
}
else
{ now->son[i]->next=T;
T->V.push_back(now->son[i]);
}
Q.push(now->son[i]);
}
}
trie *now=T;
for(int i=0; A[i]!=0; ++i)
{ while(now && now->son[A[i]-'a']==0) now = now->next;
if(!now) now = T;
else
{ now=now->son[A[i]-'a']; ++now->val;}
}
Dfs(T);
for (int i=1; i<=N; ++i) g<<where[i]->val<< '\n';
g.close();
}