Cod sursa(job #205486)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 1 septembrie 2008 10:24:49
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.63 kb
# include <stdio.h>
# include <string.h>

using namespace std;

# define FIN "abc2.in"
# define FOUT "abc2.out"
# define DMAX 10000010
# define LMAX 21
# define Nod 1000010
# define Sigma 3
# define uc unsigned char

int N=1,len,i,state,j,ok,Sol,k,l;

int Q[Nod][Sigma];
int U[Nod][Sigma];
int stack[Nod];
int Fail[Nod];
uc Ac[Nod];

char D[DMAX];
char s[LMAX];

     void trie(char *s)
     {
         state = 1;
         for (char *c = s; *c ; ++c)
           {
              i = *c - 'a';     
              if (Q[state][i])
                state = Q[state][i];
              else
                {
                   Q[state][i] = ++N;   
                   state = N;
                }
           }
         Ac[N] = 1;
     }
     
     void compute(char *s)
     {
         state = 1;
         for (char *c = s; *c ; ++c)
           {
              i = *c - 'a';
              state = U[state][i];
              Sol += Ac[state];
           }
     }
     
     void failure()
     {
         int sf = 0,u,i; 
         for (i = 0; i < 3; ++i)
           {
              U[1][i] = 1;
              if (Q[1][i] != 1)
                {
                   stack[sf++]=Q[1][i];
                   Fail[Q[1][i]] = 1;
                   U[1][i] = Q[1][i];
                }
           }
         
         for (i = 0; i < sf; ++i)
           {
              for (j = 0; j < 3; ++j)
                if (Q[stack[i]][j])
                  {
                     stack[sf++] = Q[stack[i]][j];
                     u = Fail[stack[i]];
                     while (Q[u][j] == 0)
                        u = Fail[u];
                     Fail[Q[stack[i]][j]] = Q[u][j];
                     if (Ac[Fail[Q[stack[i]][j]]] == 1)
                        Ac[Q[stack[i]][j]] = 1;
                  }
                      
              for (l = 0; l < Sigma; ++l)
                {
                  if (Q[stack[i]][l] != 0)
                    U[stack[i]][l]=Q[stack[i]][l];
                  else
                    U[stack[i]][l]=U[Fail[stack[i]]][l];
                  if (U[stack[i]][l] == 0)
                    U[stack[i]][l] = 1;
                }
           }
     }

     int main()
     {
         freopen(FIN,"r",stdin);
         freopen(FOUT,"w",stdout);
         
         scanf(" %s ",D);
         for (l = 0; scanf(" %s ",s) != EOF; )
           trie(s);
         
         for (i = 0; i < 3; ++i)
           if (Q[1][i] == 0) Q[1][i] = 1;
           
         failure();
         
         compute(D);
         
         printf("%d",Sol);
         
         return 0;
     }