Pagini recente » Cod sursa (job #2274435) | Cod sursa (job #1586333) | Cod sursa (job #1089925) | Cod sursa (job #3227113) | Cod sursa (job #3288948)
#include <fstream>
#include <cstring>
#define dim 10000
#define si short int
using namespace std;
ifstream fin ("ahocorasick.in");
ofstream fout ("ahocorasick.out");
int n,qr,m,f,l,sol[dim+1];
char str[100*dim+2],s[dim+2];
struct trie
{
trie *nxt[26],*fb;
char pos;
int sol;
trie ()
{
for (int i=0; i<26; i++)
nxt[i]=NULL;
fb=NULL;
pos=sol=0;
}
};
trie *r=new trie;
trie* q[100*dim+2];
void add (trie *r,char s[],int n,char pos)
{
for (int i=0; i<n; i++)
{
if (r->nxt[(si)s[i]]==NULL)
r->nxt[(si)s[i]]=new trie;
r=r->nxt[(si)s[i]];
}
r->pos=pos;
}
void calc_fb (trie *r)
{
q[l]=r;
r->fb=r;
while (f<=l)
{
trie *p=q[f++];
for (int i=0; i<26; i++)
{
if (p->nxt[i]!=NULL)
{
q[++l]=p->nxt[i];
if (p!=r)
{
trie *pos=p->fb;
while (pos!=r&&pos->nxt[i]==NULL)
pos=pos->fb;
if (pos->nxt[i]!=NULL)
pos=pos->nxt[i];
p->nxt[i]->fb=pos;
}
else
p->nxt[i]->fb=r;
}
}
}
}
void solve (trie *r,char s[],int n)
{
trie *p=r;
for (int i=0; i<n; i++)
{
while (p!=r&&p->nxt[(si)s[i]]==NULL)
p=p->fb;
if (p->nxt[(si)s[i]]!=NULL)
{
p=p->nxt[(si)s[i]];
p->sol++;
}
}
}
void propagate ()
{
for (int i=l; i>0; i--)
{
if (q[i]->pos!=0)
sol[(si)q[i]->pos]+=q[i]->sol;
if (q[i]->fb!=r)
q[i]->fb->sol+=q[i]->sol;
}
}
void read ()
{
fin>>str;
n=strlen (str);
for (int i=0; i<n; i++)
str[i]-='a';
fin>>qr;
for (int i=1; i<=qr; i++)
{
fin>>s;
m=strlen (s);
for (int j=0; j<m; j++)
s[j]-='a';
add (r,s,m,i);
}
}
void print ()
{
for (int i=1; i<=qr; i++)
fout<<sol[i]<<"\n";
}
int main()
{
read ();
calc_fb (r);
solve (r,str,n);
propagate ();
print ();
return 0;
}