Pagini recente » Cod sursa (job #3194870) | Cod sursa (job #915525) | Cod sursa (job #1677570) | Cod sursa (job #1824832) | Cod sursa (job #2877629)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");
struct ahocor
{
int val;
vector <int> cuv;
ahocor *fiu[26],*fail;
ahocor()
{
val=0;
fail=0;
memset(fiu,0,sizeof(fiu));
}
}*p;
ahocor *t=new ahocor;
vector <ahocor*> q;
void ahoc_insert(ahocor *t,char *c,int k)
{
if(isalpha(*c)==0)
{
t->cuv.push_back(k);
return;
}
int ch=*c-'a';
if(t->fiu[ch]==0)
t->fiu[ch]=new ahocor;
ahoc_insert(t->fiu[ch],c+1,k);
}
void make_fails(ahocor *t)
{
int st=0;
for(int i=0;i<26;i++)
if(t->fiu[i]!=0)
{
t->fiu[i]->fail=t;
q.push_back(t->fiu[i]);
}
while(st<q.size())
{
ahocor *k=q[st];
st++;
for(int i=0;i<26;i++)
if(k->fiu[i]!=0)
{
q.push_back(k->fiu[i]);
ahocor *v=k->fail;
while(v->fiu[i]==0)
v=v->fail;
k->fiu[i]->fail=v->fiu[i];
}
}
}
int sol[111];
void anti_bfs()
{
for(int i=q.size()-1;i>=0;i--)
{
ahocor *k=q[i];
if(k->fail!=0)
k->fail->val=k->fail->val+k->val;
for(int j=0;j<k->cuv.size();j++)
sol[k->cuv[j]]=k->val;
}
}
char C[1000011],c[10011];
int n,i,m,l;
int main()
{
f>>C;
f>>n;
for(i=1;i<=n;i++)
{
f>>c;
ahoc_insert(t,c,i);
}
make_fails(t);
p=t;
m=strlen(C);
for(i=0;i<m;i++)
{
l=C[i]-'a';
while(p!=t && p->fiu[l]==0)
p=p->fail;
if(p->fiu[l]!=0)
p=p->fiu[l];
p->val++;
}
anti_bfs();
for(i=1;i<=n;i++)
g<<sol[i]<<'\n';
return 0;
}