Cod sursa(job #471717)

Utilizator Bogdan_CCebere Bogdan Bogdan_C Data 20 iulie 2010 14:56:17
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.79 kb
#include<stdio.h>
#include<queue>

using namespace std;

#define FIN "abc2.in"
#define FOUT "abc2.out"
#define NMAX 10000003
#define LMAX 31

struct trie
 {
        bool T;
        int CT;
        int ORD;
        trie *NEXT[3];
        trie* UP;
        trie()
        {
            T = false;
            CT = 0;
            ORD = 0;
            NEXT[0] = NULL;
            NEXT[1] = NULL;
            NEXT[2] = NULL;
            UP = NULL; 
            }
        };

typedef trie* Nod;
Nod ROOT;
int N,rez = 0 , contor = 0 , viz[NMAX];
char SIR[NMAX];
char TEMP[21];
queue<Nod> Q , C;

void insert( Nod &nod , char* s )
 {
       if(nod -> ORD == 0) nod -> ORD = ++contor; 
       if ( *s == '\n' ) 
        {
            nod -> T = true;
            return;
            } 
       if( !nod -> NEXT[*s - 'a']) nod -> NEXT[*s - 'a'] = new trie;
       insert(nod -> NEXT[*s - 'a'] , s + 1 );     
    }        

void bfs(Nod nod)
{
    C.push(nod);
    while(!C.empty())
     {
            Nod aux = C.front();
              printf("%d %d %d\n",aux -> ORD , aux -> UP -> ORD,aux -> CT);
            C.pop();
            for(int i = 0 ; i <= 2 ; ++i)
             if( aux -> NEXT[i] )
              {
                    if(aux -> NEXT[i] -> T) aux -> NEXT[i] -> CT = aux -> NEXT[i] -> UP -> CT + 1;
                    else  aux -> NEXT[i] -> CT = aux -> NEXT[i] -> UP -> CT ;
                    C.push(aux -> NEXT[i]);
                    }
            }
    }

void construct()
{
   ROOT -> UP = ROOT;
   for(int i = 0 ; i <= 2 ; ++i)
    if( ROOT -> NEXT[i] ) Q.push(ROOT -> NEXT[i]) , ROOT -> NEXT[i] -> UP = ROOT;
   while(! Q.empty()) 
    {
       Nod aux = Q.front();
       Q.pop();
       for(int i = 0 ;i <= 2 ; ++i)
       if( aux -> NEXT[i])
         {
            Q.push(aux -> NEXT[i]);
            Nod v = aux -> UP;   
            while( !v -> NEXT[i] && v != ROOT ) v = v -> UP;
            if(v -> NEXT [i] == NULL) aux -> NEXT[i] -> UP = ROOT;
            else aux -> NEXT[i] -> UP = v -> NEXT[i];
                }
        }          
 }   

int solve()
 { 
   int poz = 0;
   Nod act = ROOT; 
   while(SIR[poz] != '\n')
    { 
        if( act == ROOT && !act -> NEXT[SIR[poz] - 'a']) poz++;
        if( !act -> NEXT[SIR[poz] - 'a']) 
           act = act -> UP;
        else 
          { act = act -> NEXT[SIR[poz] - 'a'], poz++;
        if(act -> T)  rez ++;           
          }
        } 
     return rez;   
    }    

int main()
{
    freopen(FIN,"r",stdin);
    freopen(FOUT,"w",stdout);
    fgets(SIR , NMAX , stdin);
    ROOT = new trie;
    while(fgets(TEMP , LMAX , stdin)>0 )
     {
       insert(ROOT , TEMP);     
            }
    construct();
    printf("%d",solve());        
    return 0;
    }