Cod sursa(job #823513)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 25 noiembrie 2012 09:23:51
Problema Aho-Corasick Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.16 kb
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
struct node
{bool final;
int appereances;
node *pref,*link[26],*nextDictWord;
vector<int> wordnr; 
node()
     {memset(this,0,sizeof(node)),memset(link,0,26),
     final=appereances=0,nextDictWord=NULL;}};
node *root=new node(),*currentnode;
int i,n,b[101],j;
char s[1000001],a[10001];
vector<node*> ordbf;

node *linknode(node *r,char x)
{if(!r->link[x-'a'])
     r->link[x-'a']=new node();
return r->link[x-'a'];}

void setfinal(node *r,int x)
{r->final=true,r->wordnr.push_back(x);}

void add(char *s,int wordnr)
{node *currentnode=root;
root->final=true;
for(int i=0;s[i];i++)
       currentnode=linknode(currentnode,s[i]);
setfinal(currentnode,wordnr);}

void ac(node *root)
{int i;
queue<node*> coada;
for(i=0;i<26;i++)
if(root->link[i])
      coada.push(root->link[i]),ordbf.push_back(root->link[i]),root->link[i]->pref=root;
node *tata,*fiu,*aux;
while(!coada.empty())
      {tata=coada.front(),coada.pop();
      for(i=0;i<26;i++)
      if(tata->link[i])
            {fiu=tata->link[i],aux=tata->pref;
            coada.push(fiu),ordbf.push_back(fiu);
            for(aux=tata->pref;aux&&!aux->link[i];aux=aux->pref);
            fiu->pref=aux->link[i];
            if(!aux)
		          fiu->pref=root;
            for(aux=fiu->pref;aux&&!aux->final;aux=aux->pref);
            fiu->nextDictWord=aux;}}}

int main()
{freopen("ahocorasick.in","r",stdin),freopen("ahocorasick.out","w",stdout);
gets(s),scanf("%d\n",&n);
for(j=1;j<=n;j++)
	gets(a),add(a,j);
ac(root),currentnode=root;
for(i=0;s[i];i++)
    {while(!currentnode->link[s[i]-'a']&&currentnode!=root)
            currentnode=currentnode->pref;
    if(currentnode->link[s[i]-'a'])
            currentnode=currentnode->link[s[i]-'a'],currentnode->appereances++;}
for(i=0;i<ordbf.size();i++)
if(ordbf[i]->final)
    {if(ordbf[i]->nextDictWord!=root&&ordbf[i]->nextDictWord)
            ordbf[i]->nextDictWord->appereances+=ordbf[i]->appereances;
    for(j=0;j<ordbf[i]->wordnr.size();j++)
            b[ordbf[i]->wordnr[j]]=ordbf[i]->appereances;}
for(i=1;i<=n;i++)
     printf("%d\n",b[i]);
return 0;}