Cod sursa(job #798878)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 17 octombrie 2012 15:08:40
Problema Aho-Corasick Scor 55
Compilator cpp Status done
Runda Arhiva educationala Marime 2.71 kb
#include<cstdio>
#include<cstring>
struct edge
{char c;
struct node *next;};

typedef struct node
{int d,mpn,od,ann;
struct node *fn,**an; 
char **mp;
struct edge *o;}N_t;

N_t *r,*next,*thiz=new N_t;
int i,n,b[101],j,k,o[101];
char s[1000002],a[101][10002],c[102];

N_t *find_next(N_t *thiz,char c)
{for(int i=0;i<thiz->od;i++)
if(thiz->o[i].c==c)
    return thiz->o[i].next;
return NULL;}

int has_matchstr(N_t *thiz,char *newstr)
{for(int i=0;i<thiz->mpn;i++)
	{char *str=thiz->mp[i];
    if(strlen(str)!=strlen(newstr))
			continue;
	for(int j=0;j<strlen(str);j++)
	if(str[j]==newstr[j])
			return 1;}
return 0;}

N_t *create_next(N_t *thiz,char c)
{if(find_next(thiz,c))
	return NULL;	
N_t *next=new N_t;
memset(next,0,sizeof(N_t));
next->o=new edge[8];
next->mp=new char*[102];
thiz->o[thiz->od].c=c;
thiz->o[thiz->od++].next=next;
return next;}
		
void traverse_setfailure(N_t *thiz,N_t *node,char *c)
{for(int i=0;i<node->od;i++)
	{c[node->d]=node->o[i].c;
	for(int k=1;k<node->o[i].next->d;k++)
	      {N_t *m=thiz;
          for(int j=k;j<node->o[i].next->d&&m;j++)
                 m=find_next(m,c[j]);
          if(m)
                 {node->o[i].next->fn=m;
                 break;}}
    if(!node->o[i].next->fn)
          node->o[i].next->fn=thiz;
	traverse_setfailure(thiz,node->o[i].next,c);}}

void union_matchstrs(N_t *node)
{for(N_t *m=node;(m=m->fn);)
   {for(int i=0;i<m->mpn;i++)
   if(!has_matchstr(node,m->mp[i]))
       node->mp[node->mpn++]=m->mp[i];}}

int main()
{freopen("ahocorasick.in","r",stdin),freopen("ahocorasick.out","w",stdout);
gets(s),scanf("%d\n",&n);
memset(thiz,0,sizeof(N_t));
thiz->o=new edge[8];
thiz->mp=new char*[102];
thiz->an=new N_t*[10002];
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=find_next(r,a[j][i])))
                  r=next;
           else
                  {next=create_next(r,a[j][i]);
                  next->d=r->d+1,r=next;
                  thiz->an[thiz->ann++]=r;}
           if(!has_matchstr(r,a[j]))
                  r->mp[r->mpn++]=a[j];}}
traverse_setfailure(thiz,thiz,c);
for(i=0;i<thiz->ann;i++)
	union_matchstrs(thiz->an[i]);
while(s[k])
	  {if(!(next=find_next(thiz,s[k])))
		    if(thiz->fn)
				thiz=thiz->fn;
			else
				k++;
      else
		    thiz=next,k++;
      if(next)
            {for(i=1;i<=n;i++)
            if(!o[i])
                  for(j=0;j<thiz->mpn;j++)
                  if(thiz->mp[j]==a[i])     	      
                          b[i]++;}}
for(i=1;i<=n;i++)
     printf("%d\n",!o[i]?b[i]:b[o[i]]);
return 0;}