Cod sursa(job #1730251)

Utilizator andreey_047Andrei Maxim andreey_047 Data 16 iulie 2016 17:09:12
Problema Aho-Corasick Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 1.92 kb
#include <bits/stdc++.h>

using namespace std;

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

struct Trie{

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

}*T;

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

inline void Init(Trie *T,int i,int cnt){
  int x = ch[i]-'a';

  if(T->leg[x]) {
    if(i == N-1) {T->leg[x]->ok = true;return;}
        Init(T->leg[x],i+1,cnt);
  }
  else{
    T->leg[x] = new Trie;

    if(i == N-1) {T->leg[x]->ok = cnt;return;}
    Init(T->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;

    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;
                Q.push(R->leg[i]);
            }
        }
    }
}

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;

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

            R = R->leg[x];
            if(R->ok) ++v[R->ok];
                F = R;
            while(F!=T){
                if(F->fall->ok)++v[F->fall->ok];
                F = F->fall;

        }

        }
        else R = T;
    }
    for(int i = 1; i <= q; ++i)
        printf("%d\n",v[i]);
    return 0;
}