Cod sursa(job #798803)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 17 octombrie 2012 12:42:10
Problema Aho-Corasick Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 2.85 kb
#include<cstdio>
#include<cstring>
typedef struct
{char *a,*y; 
int l,x;}P_t;

struct edge
{char c;
struct node *next;};

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

N_t *r,*next,*thiz=new N_t;
int i,n,b[105],j,k,o[105];
char s[1000005],a[105][10005],c[1024];

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,P_t *newstr)
{for(int i=0;i<thiz->mpn;i++)
	{P_t *str=&thiz->mp[i];
    if(str->l!=newstr->l)
			continue;
	for(int j=0;j<str->l;j++)
	if(str->a[j]==newstr->a[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 P_t[8];
thiz->o[thiz->od].c=c;
thiz->o[thiz->od++].next=next;
return next;}

void set_failure(N_t *thiz,N_t *node,char *c)
{for(int i=1;i<node->d;i++)
	{N_t *m=thiz;
	for(int j=i;j<node->d&&m;j++)
		m=find_next(m,c[j]);
	if(m)
		{node->fn=m;
		break;}}
if(!node->fn)
    node->fn=thiz;}
		
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;
	set_failure(thiz,node->o[i].next,c);
	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];   
   if(m->f)
       node->f=1;}}

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 P_t[8];
thiz->an=new N_t*[1000005];
thiz->an[thiz->ann++]=thiz;
P_t tmp_patt;
for(j=1;j<=n;j++)
	{gets(a[j]),tmp_patt.a=a[j];
    tmp_patt.l=strlen(a[j]),r=thiz;
    for(o[j]=0,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,&tmp_patt))
                  r->mp[r->mpn++]=tmp_patt;
           r->f=1;}}
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(thiz->f&&next)
            {for(i=1;i<=n;i++)
            if(!o[i])
                  for(j=0;j<thiz->mpn;j++)
                  if(!strcmp(thiz->mp[j].a,a[i]))     	      
                          b[i]++;}}
for(i=1;i<=n;i++)
     printf("%d\n",!o[i]?b[i]:b[o[i]]);
return 0;}