Pagini recente » Cod sursa (job #382631) | Cod sursa (job #1676528) | Cod sursa (job #2938638) | Cod sursa (job #3285797) | Cod sursa (job #1171828)
#include<fstream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
ifstream in("ahocorasick.in");
ofstream out("ahocorasick.out");
const int Nmax = 1000100;
const int Lmax = 10100;
char A[Nmax],B[Lmax];
int Many[101];
int N;
struct trie{
char c;
vector<int> is;
trie* to[27];
trie *tata,*fail,*megafail;
trie(){memset(to,0,sizeof(to));}
trie(int _c,trie* _t){c=_c,tata=_t,memset(to,0,sizeof(to));}
int isnext(char C){
int co=int(C)-'a';
return to[co]!=NULL;
}
trie* next(char C){
int co=int(C)-'a';
return to[co];
}
trie* nextad(char C){
int co=int(C)-'a';
trie* t=new trie(C,this);
to[co]=t;
return t;
}
};
trie* R;
void push(int ind,char *s){
trie* t=R;
for(char c=*s;*s;s++,c=*s){
if(t->isnext(c)) t=t->next(c);
else t=t->nextad(c);
}
t->is.push_back(ind);
}
queue<trie*> q;
trie* findfail(trie* t){
int C=t->c;
t=(t->tata)->fail;
while(t!=R && !t->isnext(C)) t=t->fail;
if(t->isnext(C)) return t->next(C);
return t;
}
trie* findmegafail(trie* t){
t=t->fail;
while(t!=R){
if(t->is.size()) return t;
t=t->fail;
}
return t;
}
void increment(trie *t){
while(t!=R){
if(t->is.size()) for(vector<int>::iterator it=t->is.begin();it!=t->is.end();++it) Many[*it]++;
t=t->fail; // no optimisation
}
}
void process(char *s){
trie* t=R;
for(char c=*s;*s;s++,c=*s){
while(t!=R && !t->isnext(c)) t=t->fail;
if(t->isnext(c)) t=t->next(c);
increment(t);
}
}
int main(){
R=new trie(0,0);
in.getline(A,Nmax);
in>>N;in.get();
for(int i=1;i<=N;i++){
in.getline(B,Lmax);
push(i,B);
}
for(int co=0;co<=25;co++){
if(R->to[co]!=NULL){
R->to[co]->fail=R;
R->to[co]->megafail=R;
q.push(R->to[co]);
}
}
while(!q.empty()){
trie* t=q.front(); q.pop();
if(!t->fail){
t->fail=findfail(t);
t->megafail=findmegafail(t);
}
for(int co=0;co<=25;co++){
if(t->to[co]!=NULL) q.push(t->to[co]);
}
}
process(A);
for(int i=1;i<=N;i++) out<<Many[i]<<'\n';
return 0;
}