Cod sursa(job #98449)

Utilizator ZeusCatalin Tiseanu Zeus Data 10 noiembrie 2007 13:34:25
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 5.5 kb

// chestii grele

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

using namespace std;

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

class Trie
{  
      
#define V 4
   public:  
       
   int ID_POOL;    
       
   class node
   {
       public:
       int id, term;
       node * to[ V ];
       
       node()
       { 
             for( int i = 0; i < V; ++i )
                  to[i] = NULL;
             id = -1;
             term = 0;
       } 
   } * R;    
   
   
   Trie()
   {
         R = new node();        
         R->id = 0; 
         ID_POOL = 1;
   }
   
   void add_dict( vector<string> w )
   {
        for( int i = 0; i < (int)w.size(); ++i )
             add_word( w[i] );
   }
   
   void add_word( string w )
   {
//         cout << "-> " << w << endl;
        
         node * at = R;
         for( int i = 0; i < (int)w.size(); ++i )    
         {
              if( at->to[ w[i] ] )
                   at = at->to[ w[i] ];
              else
              {
                   node * n = new node();
                   n->id = ID_POOL++;
                   at->to[ w[i] ] = n;
                   at = n;     
              }
         }
         at->term++;
   }
   
   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 << (char)(x);
                 print_trie( n->to[x], pos + 1 );  
                 ++nr;  
             }    
        
        if( !nr )
            cout << endl; 
   }
};

class AC
{
#define V 4
    private:
       Trie T;
       int nr_word, nr_state;   
       queue<int> Q; 
       vector<int> f, out;
       vector< vector<int> > g;
    public:       
       
       AC()
       {
             nr_word = 0;
       }
       
       void add_word( string w )
       {
             T.add_word( w );
       }        
       
       void add_dict( vector<string> w )
       {
            T.add_dict( w );     
       }
       
       void debug()
       {
            T.print_trie( T.R, 0 );     
       }
       
       void df( Trie::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()
       {
             nr_state = T.ID_POOL; 
             
             f.resize( nr_state ), out.resize( nr_state );
             
             g.resize( nr_state );
             for( int i = 0; i < nr_state; ++i )
                  g[i].resize( V );
             
             df( T.R );
             
             for( int x = 0; x < V; ++x )
                  if( T.R->to[x] )
                      f[ T.R->to[x]->id ] = 0,
                      Q.push( T.R->to[x]->id );
             
             while( (int)Q.size() )
             {
                  int r = Q.front(), u, v; Q.pop();
                                       
                  for( int x = 0; x < V; ++x )
                       if( (u=g[ r ][ x ]) != -1 ) // u is the son of r with edge x
                       {
                            Q.push( u ); 
                            v = f[ r ];
                            
                            while( g[ v ][ x ] == -1 )
                                   v = f[ v ];
                            
                            f[ u ] = g[ v ][ x ];
                            out[ u ] = out[ u ] + out[ f[u] ]; 
                       }
                                
             }
       }

       inline int process_character( int & q, char x )
       {
            while( g[ q ][ x ] == -1 )
                q = f[ q ];    
            q = g[ q ][ x ];
            return out[ q ];
       }
       
       int process_string()
       {
            int v, q = 0, nr_found = 0;  
                 
            for( int i = 0; i < L; ++i )
            {
                 v = process_character( q, A[i] );
//                 cout << "pos : " << i << " found " << v << endl;
                 nr_found += (v?1:0);
            }       
            
            return nr_found;
       }
} MyAC;

int main()
{
    freopen("abc2.in", "r", stdin);
    freopen("abc2.out", "w", stdout);
    
    int i, j, l, k;
    
    gets( A );
    L = strlen( A );
    
    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' - 1;
    for( i = 1; i <= N; i++ )    
         for( l = 0; l < M; l++ ) cuv[i][l] -= 'a' - 1;
    
    for( int i = 1; i <= N; i++ )
         MyAC.add_word( string(cuv[i]) );
    MyAC.build_automata();
    cout << MyAC.process_string() << endl;

    return 0;    
}