Cod sursa(job #1730384)

Utilizator andreey_047Andrei Maxim andreey_047 Data 16 iulie 2016 20:58:30
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.99 kb
#include <bits/stdc++.h>

using namespace std;

const int nmax = 1e6+2; const int cmax = 10005;

struct Trie{

 Trie *leg[26],*fall;
 vector<int>p;
 int ok,num;
 Trie(){
     ok = num = 0;
     fall = NULL;
   for(int i = 0; i < 26; ++i)
    leg[i] = NULL;
 }

}*T,*d[10005];

queue<Trie*>Q;
char t[nmax],ch[cmax];
int q,N,v[105],lg;

inline void Init(Trie *R,int i,int cnt){
  int x = ch[i]-'a';
  if(R->leg[x] == NULL)
        R->leg[x] = new Trie;

    if(i == N-1) {R->leg[x]->p.push_back(cnt);return;}

  Init(R->leg[x],i+1,cnt);
}

inline void Bfs(){
    int i;
    Trie *R,*F;

    for(i = 0; i < 26; ++i)
        if(T->leg[i])Q.push(T->leg[i]),T->leg[i]->fall = T,d[++lg] = T->leg[i];

    while(!Q.empty()){
        R = Q.front();
        Q.pop();

        for(i = 0; i < 26; ++i)
            if(R->leg[i]){

                F = R->fall;
                while(F != T &&  F->leg[i] == NULL)F = F->fall;

                if(F->leg[i])R->leg[i]->fall = F->leg[i];
                else R->leg[i]->fall = T;
                d[++lg] = R->leg[i];
                Q.push(R->leg[i]);

            }

    }
}

inline void atac(){
    Trie *R;
    while(lg){
        R = d[lg];
        if(R->fall)R->fall->num+=R->num;
        for(int i = 0; i < R->p.size();++i)v[R->p[i]] = R->num;
        --lg;
    }
}

int main(){
    ios::sync_with_stdio(false);

    freopen("ahocorasick.in","r",stdin);
    freopen("ahocorasick.out","w",stdout);

    scanf("%s\n%d\n",t,&q);
    T = new Trie;

    for(int i = 1; i <= q; ++i){
        scanf("%s",ch); N = strlen(ch);
        Init(T,0,i);
    }
    Bfs();
    Trie* R = T,*F;
    int x;
    int g = strlen(t);

    for(int i = 0; i < g; ++i){
            x = t[i] - 'a';
        while(R != T && R->leg[x] == NULL)R = R->fall;

        if(R->leg[x])
            R = R->leg[x];
          ++R->num;
        }
    atac();
    for(int i = 1; i <= q; ++i)
        printf("%d\n",v[i]);
    return 0;
}