Cod sursa(job #935195)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 1 aprilie 2013 23:59:03
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.32 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

#define Smax 1000005
#define Lmax 10005
#define Nmax 105
#define Sigma 26

struct TRIE{

    TRIE *fiu[Sigma], *fail;

    int potriviri;
    vector <int> nd;

    TRIE(){

        potriviri = 0;
        fail = NULL;
        memset(fiu, 0, sizeof(fiu));
    }
};

TRIE *T, *Q[ Nmax * Lmax ], *P;

char S[Smax], L[Lmax];
int REZ[Nmax];
int inc, sfc , N;


void adauga ( TRIE *T, char *p, int i ){

    if ( !isalpha( *p ) ){

        T -> nd.push_back(i);

        return;
    }

    int next = *p - 'a';

    if ( T -> fiu[next] == 0 )
            T -> fiu[next] = new TRIE;

    adauga ( T -> fiu[next], p + 1, i );
}

void BFS( TRIE *T ){

    TRIE *tmp;
    T -> fail = T;

    for ( Q[ inc = sfc = 1 ] = T; inc <= sfc; inc++ ){

        TRIE *cr = Q[inc];

        for ( int i = 0; i < Sigma; i++ )
            if ( cr -> fiu[i] != NULL ){

                for ( tmp = cr -> fail; tmp != T && tmp -> fiu[i] == NULL; tmp = tmp -> fail );

                if( tmp -> fiu[i] != NULL && tmp -> fiu[i] != cr -> fiu[i] )
                    tmp = tmp -> fiu[i];

                cr -> fiu[i] -> fail = tmp;
                Q[ ++sfc ] = cr -> fiu[i];
            }
    }

    T -> fail = NULL;
}

void RevBFS( TRIE *T ){

    for ( int i = sfc; i; i-- ){

        TRIE *cr = Q[i];

        if ( cr -> fail != NULL )
            cr -> fail -> potriviri += cr -> potriviri;

        for ( unsigned int j = 0; j < cr -> nd.size(); j++ )
            REZ[ cr -> nd[j] ] = cr -> potriviri;
    }
}

int main(){

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

    scanf("%s", S);
    scanf("%d", &N);

    T = new TRIE;

    for ( int i = 1; i <= N; ++i ){

        scanf("%s", L);
        adauga( T, L, i );
    }

    BFS( T );

    P = T;
    int lg = strlen( S );

    for ( int i = 0; i < lg; ++i ){

        int next = S[i] - 'a';

        for ( ; P -> fiu[next] == NULL && P != T; P = P -> fail );

        if ( P -> fiu[next] != NULL )
            P = P -> fiu[next];

        ++P -> potriviri;
    }

    RevBFS( T );

    for ( int i = 1; i <= N; ++i )
        printf("%d\n", REZ[i]);

    return 0;
}