Cod sursa(job #1308907)

Utilizator bogdanpaunFMI Paun Bogdan Gabriel bogdanpaun Data 4 ianuarie 2015 20:48:58
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
#include <cstdio>
#include <cstring>
#include <map>
#include <string>
using namespace std;

char text[10000009];
char cuvant[25];
int i,n,j;

struct trie{
    trie *fiu[3],*fail;
    int nr;
    trie(){
        memset(fiu,0,sizeof(fiu));
        nr = 0; fail = NULL;
    }
};

trie  *t = new trie,*q[400000000],*ult,*nod;
//trie *punct_final_cuvant[50050]
map< string , trie* > m;


void insert(trie *nod,char *c){
    if( *c == '\0' ){
        //punct_final_cuvant[i] = nod;
        ult = nod;
        return ;
    }
    if( nod->fiu[ *c - 'a' ] == NULL ) nod->fiu[ *c - 'a' ] = new trie;
    insert( nod->fiu[ *c - 'a' ] , c+1 );
}

int main()
{
    freopen("abc2.in" , "r" , stdin);
    freopen("abc2.out", "w" , stdout);

    scanf("%s", text);

    while( !feof(stdin) ){
        scanf("%s",  cuvant);
        if( m.find( string(cuvant) ) != m.end() ) continue;
        ++i;
        //insert( t , cuvant );
        j = 0; nod = t;
        while( cuvant[j] != '\0' ){
            if( nod->fiu[ cuvant[j] - 'a' ] == NULL ) nod->fiu[ cuvant[j] - 'a' ] = new trie;
            nod = nod->fiu[ cuvant[j] - 'a' ];
            ++j;
        }

        m[ string(cuvant) ] = nod;
    }/////////////////////////////////////////////////////////////
    n = i;
    trie *nod, *fail;
    t->fail=t;
    int inc , fin;
    for( q[inc=fin=1] = t; inc <= fin ; ++inc ){
        nod = q[inc];
        for(i=0 ; i <3 ; ++i)
            if( nod->fiu[i] ){
                    for(fail = nod->fail; fail != t && fail->fiu[i] == 0; fail = fail->fail);
                    if( fail->fiu[i] != NULL && fail != nod ) fail = fail->fiu[i];
                    nod->fiu[i]->fail = fail;
                    q[++fin] = nod->fiu[i];
            } /////////////////////////////////////////////////////
    } ////////////////////////////////////////////////////////////

    trie *p = t;
    t->fail = NULL;
    int len = strlen(text) , k;
    for(i = 0;i < len; ++i){
        k = text[i] - 'a';
        for( ; p->fiu[k] == NULL && p != t; p = p->fail);
        if( p->fiu[k] ) p = p->fiu[k];
        ++p->nr;
    }
    for(i = fin ; i ; --i){
        nod=q[i];
        if( nod->fail != NULL ) nod->fail->nr += nod->nr;
    }
    int sum = 0;
    for( map< string , trie* >::iterator it = m.begin() ; it != m.end() ; ++it )
        sum += it->second->nr;
    printf("%d",sum);

    return 0;
}