Cod sursa(job #823490)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 25 noiembrie 2012 01:58:31
Problema Aho-Corasick Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 2.17 kb
#include<cstdio>
#include<cstring>
struct P
{int b;
char* a;};

struct T
{int f,d,mpn,ann,e;
T *fn,**an; 
char **mp;
T *o[26];
T()
     {memset(this,0,sizeof(T)),mp=new char*[101];
     for(int i=0;i<26;i++)
           o[i]=0;}};

T *m,*r,*next,*thiz=new T();
int i,n,b[101],j,k,o[101],l;
char s[1000001],a[101][10001],c[10001];
P d[101];

int has(T *thiz,char c[])
{int i,j,k=strlen(c);
for(i=0;i<thiz->mpn;i++)
if(strlen(thiz->mp[i])==k)
     for(j=0;j<k;j++)
     if(thiz->mp[i][j]==c[j])
           return 1;
return 0;}
		
void failure(T *thiz,T *node,char c[])
{for(int i=0,j,k,l;i<26;i++)
if(node->o[i])
	{c[node->d]=i+'a';
	T *r=node->o[i],*m;
	if(!r->fn)
	        r->fn=thiz;
    for(l=j=1;j<r->d&&l;j++)
            {m=thiz;
            for(k=j;k<r->d&&m;m=m->o[c[k++]-'a']);
            if(m)
                   r->fn=m,l=0;}
    failure(thiz,r,c);}}

int main()
{freopen("ahocorasick.in","r",stdin),freopen("ahocorasick.out","w",stdout);
gets(s),scanf("%d\n",&n);
thiz->an=new T*[10001],thiz->an[thiz->ann++]=thiz;
for(j=1;j<=n;j++)
	{gets(a[j]),r=thiz;
    for(i=1;i<j&&!o[j];i++)
    if(!strcmp(a[j],a[i]))
           o[j]=i;
    if(!o[j])
           {for(i=0;a[j][i];i++)
           if((next=r->o[a[j][i]-'a']))
                  r=next;
           else
                  next=new T(),r->o[a[j][i]-'a']=next,
                  next->d=r->d+1,thiz->an[thiz->ann++]=r=next;
           if(!has(r,a[j]))
                  r->mp[r->mpn++]=a[j];
           r->f=1;}}
failure(thiz,thiz,c);
for(i=1;i<=n;i++)
if(!o[i])
      d[l].a=a[i],d[l++].b=i;
for(i=0;i<thiz->ann;i++)
for(m=thiz->an[i];(m=m->fn);)
      {for(j=0;j<m->mpn;j++)
      if(!has(thiz->an[i],m->mp[j]))
            thiz->an[i]->mp[thiz->an[i]->mpn++]=m->mp[j];   
      if(m->f)
            thiz->an[i]->f=1;}
while(s[k])
      {while(!(next=thiz->o[s[k]-'a'])&&thiz->fn)
             thiz=thiz->fn;
      thiz=next,k++;
      if(thiz->f)
             for(i=0;i<l;i++)
             for(j=0;j<thiz->mpn;j++)
             if(thiz->mp[j]==d[i].a)     	      
                   b[d[i].b]++;}
for(i=1;i<=n;i++)
     printf("%d\n",!o[i]?b[i]:b[o[i]]);
return 0;}