Cod sursa(job #98625)

Utilizator ZeusCatalin Tiseanu Zeus Data 10 noiembrie 2007 15:16:22
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 5.22 kb

// chestii grele

#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <queue>
#include <set>

#define RUN_IT

using namespace std;

int N, M, L, ret;
char A[10111111], cuv[50111][22];
clock_t start, end;

void clock_it( string x )
{
#ifndef RUN_IT
     clock_t at = clock();
     cout << x << " = " << 1.0 * ( at - start ) / CLOCKS_PER_SEC << endl;
#endif
}

#define V 3
       
   struct node
   {
       char term;
       node * to[ V ], *f;
       
       node()
       { 
             for( int i = 0; i < V; ++i )
                  to[i] = NULL;
             term = 0;
       } 
   } * R;    
   
   void t_init()
   {
         R = new node();        
   }
   
   void t_add_word( char * s )
   {
         node * at = R;
         for( int i = 0; i < M; ++i )    
         {
              if( at->to[ s[i] ] )
                   at = at->to[ s[i] ];
              else
              {
                   node * n = new node();
                   at->to[ s[i] ] = n;
                   at = n;     
              }
         }
         at->term = 1;
   }
   
   void print_trie( node * n, int pos)
   {
        int nr(0);
        
        for( int x = 0; x < V; ++x )
             if( n->to[x] )
             {
                 if( nr )
                     cout << string( pos, ' ' );
                 
                 cout << (int)(x);
                 print_trie( n->to[x], pos + 1 );  
                 ++nr;  
             }    
        
        if( !nr )
            cout << endl; 
   }

#define MAX_SZ 888999
//int f[MAX_SZ];
//char out[MAX_SZ];
//int g[MAX_SZ][V];

node * Q[MAX_SZ];
  
       int nr_word, nr_state;   
/*       
       void df( node * n )
       {
            for( int x = 0; x < V; x++ )
            {
                 if( n->to[x] )
                 {
                     g[ n->id ][ x ] = n->to[x]->id;
                     df( n->to[x] ); 
                 }
                 else
                 {
                     if( n->id == 0 ) // root
                         g[ 0 ][ x ] = 0;
                     else
                         g[ n->id ][ x ] = -1;
                 }
            }     
            
            out[ n->id ] = n->term;   
       }
*/       
       void build_automata()
       {
#ifndef RUN_IT
             cout << "Nr_state = " << nr_state << endl;
#endif
             clock_it( "Resizing" );
               
             clock_it( "df" );
             
             int left = 0, right = -1;
             
             for( int x = 0; x < V; ++x )
                  if( R->to[x] )
                      R->to[x]->f = R,
                      Q[ ++right ] = R->to[x];
             
             clock_it( "graph" );
             
             for( ; left <= right; left++ )
             {
                  node * r = Q[ left ], *u, *v; 
                                       
                  for( int x = 0; x < V; ++x )
                       if( (u=r->to[x]) ) // u is the son of r with edge x
                       {
                            Q[ ++right ] = u;
                            v = r->f;
                            
                            while( !v->to[x] )
                                   v = v->f;
                            
                            u->f = v->to[x];
                            u->term |= u->f->term;
                       }        
             }
             
             clock_it( "queue" );
       }

void gen()
{
    srand(23); 
     
    freopen("abc2.in", "w", stdout); 

    L = 10000000, N = 50000, M = 20;
    
    for( int i = 0; i < L; i++ )
         printf("%c", (char)( 'a' + rand() % 3 ) ); printf("\n");

    string aux( ' ', M );

    for( int c = 0; c < N; c++ )
    {
         for( int i = 0; i < M; i++ )
              aux[i] = (char)( 'a' + rand() % 3 );
         for( int i = 0; i < M; i++ )
              printf("%c", aux[i] ); printf("\n");
    }

}

int main()
{
//    gen();
    
    freopen("abc2.in", "r", stdin);
    freopen("abc2.out", "w", stdout);
    
    start = clock();
    
    int i, j, l, k;
    
    gets( A );
    L = strlen( A );
    
    N = 0;
    while( gets( cuv[++N] ) );
    --N;
    
    if( N == 0 )
    {
        printf("0\n");
        return 0;    
    }
    
    M = strlen(cuv[1]);
    
    if( M > L )
    {
        printf("0\n");
        return 0;   
    } 

    for( l = 0; l < L; l++ ) 
         A[l] -= 'a';
    for( i = 1; i <= N; i++ )    
         for( l = 0; l < M; l++ ) 
              cuv[i][l] -= 'a';
    
    clock_it( "reading" );
        
    t_init();    
    for( int i = 1; i <= N; i++ )
         t_add_word( cuv[i] );
    build_automata();


//    cout << MyAC.process_string() << endl;

    int q = 0; int x;
    node * m = R;
    
    clock_it( "starting string processing" );

    for( i = 0; i < L; ++i )
    {
         x = (int)A[i];
         for( ; !m->to[x]; m = m->f );
         m = m->to[x];
         ret += (int)m->term;
    }  

    cout << ret << endl;

    clock_it( "total" );

    return 0;    
}