Cod sursa(job #1840332)

Utilizator CodrutLemeniCodrut Lemeni CodrutLemeni Data 4 ianuarie 2017 11:46:12
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.54 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
#include <queue>
#define LMAX 1000010
#define LEN 100010
#define LENDIC 26
#define NRCUV 110

using namespace std;

struct tries{
    vector <tries *> adj;
    int nrcuv;
    tries *alf[LENDIC] , *fail  ;

    tries(){
        nrcuv = 0;
        adj.clear();
        fail = NULL;
        for ( int i =0 ; i < LENDIC ; i++ ){
            alf[i] =NULL ;
        }
    }

};


struct tries *tr = new tries , *cur , *sol[NRCUV] ;


int k;
char s [LEN] , sircmp [LMAX] ;
tries* ins (  int i , tries *a ){

    if ( s[i] == 0 ){
        return a;
    }


    if ( a->alf [ s[i]- 'a'] == 0 ){
        a->alf[ s[i] - 'a' ] = new tries;
    }

    return ins( i + 1 , a->alf[ s[i]- 'a' ] );

}


queue <tries*> que;

void bfs (  ){

    //t->fail = t ;
    que.push ( tr );

    while ( !que.empty() ){

        tries *node = que.front();
        que.pop();

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

            if ( node->alf[i] == NULL ){
                continue ;
            }

            tries *temp = node->fail ;

            while ( temp && temp->alf[i] == NULL ){
                temp = temp->fail ;
            }

            if( temp == NULL ){
                temp = tr ;
            }else{
                temp = temp->alf[i];
            }

            node->alf[i]->fail = temp;
            temp->adj.push_back( node->alf[i] );

            que.push( node->alf[i] );

        }

    }


}


int dfs( tries *nod ) {
    vector < tries* > :: iterator it;
    int nrsubarb = 0 ;

    for ( it = nod->adj.begin() ; it != nod->adj.end() ; it++ ){
        dfs( *it );
        nod ->nrcuv += (*it)->nrcuv;
    }




    return nrsubarb ;
}

int main(){
    int n;

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

    scanf("%s",sircmp);

    scanf("%d",&n);

    for ( k = 0 ; k < n ;  k ++ ){
        scanf("%s", s);
        sol[k] = ins( 0 , tr);
    }

    bfs ();

    cur = tr;
    for ( int i = 0 ; sircmp[ i ] ; i ++  ){

        while ( cur && cur->alf[ sircmp [i] - 'a' ] == NULL  ){
            cur = cur->fail;
        }

        if( cur == NULL ){
            cur = tr ;
        }else {
            cur = cur->alf[ sircmp[i] - 'a' ];
        }
        cur->nrcuv ++;
    }

    dfs( tr );

    for ( int i = 0 ; i <   n ; i++ ){
        printf("%d\n", sol[i]->nrcuv );
    }


    return 0;
}