Cod sursa(job #1954636)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 5 aprilie 2017 15:44:21
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.05 kb
#include <bits/stdc++.h>
#define MAXA 1000000
#define MAXB 10000
#define SIGMA 26
FILE *fi,*fout;
char A[MAXA+1];
char B[MAXB+2];
inline int read(char *str){
   char ch=fgetc(fi);
   while(!isalpha(ch))
     ch=fgetc(fi);
   int sz=0;
   while(isalpha(ch)){
      str[++sz]=ch;
      ch=fgetc(fi);
   }
   return sz;
}
struct Aho{
   Aho *son[SIGMA];
   Aho *fail;
   std::vector <int> poz;
   int cnt;
   Aho(){
      memset(son,0,sizeof(son));
      fail=0;
      cnt=0;
   }
};
Aho *root=new Aho;
void Insert(Aho *nod,char *str,int pos){
    if(*str==-1)
      nod->poz.push_back(pos);
    else{
      char ch=*str-'a';
      if(nod->son[ch]==0)
        nod->son[ch]=new Aho;
      Insert(nod->son[ch],str+1,pos);
    }
}
Aho *Q[MAXA+1];
int e;
inline void bfs(){
   int b=0;
   e=1;
   root->fail=root;
   Q[0]=root;
   while(b<e){
      Aho *nod=Q[b];
      b++;
      for(int i=0;i<SIGMA;i++)
       if(nod->son[i]){
          Aho *x=nod->fail;
          while(x!=root&&x->son[i]==0)
            x=x->fail;
          if(x->son[i]!=nod->son[i]&&x->son[i])
            nod->son[i]->fail=x->son[i];
          else
            nod->son[i]->fail=x;
          Q[e++]=nod->son[i];
       }
   }
}
int n;
inline void solve(){
   Aho *nod=root;
   for(int i=1;i<=n;i++){
      char ch=A[i]-'a';
      if(nod->son[ch]==0)
         while(nod!=root&&nod->son[ch]==0)
           nod=nod->fail;
      if(nod->son[ch]){
         nod=nod->son[ch];
         nod->cnt++;
      }
   }
}
int sol[MAXB+1];
inline void antibfs(){
    for(int i=e-1;i>0;i--){
       Aho *nod=Q[i];
       for(int j=0;j<nod->poz.size();j++)
         sol[nod->poz[j]]=nod->cnt;
       if(nod->fail!=nod)
         nod->fail->cnt+=nod->cnt;
    }
}
int main(){
    int i,m;
    fi=fopen("ahocorasick.in" ,"r");
    fout=fopen("ahocorasick.out" ,"w");
    n=read(A);
    fscanf(fi,"%d " ,&m);
    for(i=1;i<=m;i++){
       int sz=read(B);
       B[sz+1]=-1;
       Insert(root,B+1,i);
    }
    bfs();
    solve();
    antibfs();
    for(i=1;i<=m;i++)
      fprintf(fout,"%d\n" ,sol[i]);
    fclose(fi);
    fclose(fout);
    return 0;
}