Cod sursa(job #205375)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 31 august 2008 13:04:07
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 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

uc Ac[Nod];
int Q[Nod][Sigma];
int Fail[Nod];
int N = 1,len,i,state,j,ok,Sol,k,l;
char D[DMAX];
char s[LMAX];
int stack[Nod];

     void trie(char *s)
     {
         state = 1;
         for (char *c = s; *c ; ++c)
           {
              i = *c - 'a';     
              if (Q[state][i] != 0)
                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';
              for (l = 0; Q[state][i] == 0;)
                state = Fail[state];
              state = Q[state][i];
              Sol += Ac[state];
           }
     }
     
     void failure()
     {
         int sf = 0,u,i; 
         for (i = 0; i < 3; ++i)
           if (Q[1][i] != 1)
             {
                stack[sf++]=Q[1][i];
                Fail[Q[1][i]] = 1;
             }
         
         for (i = 0; i < sf; ++i)
           for (j = 0; j < 3; ++j)
             if (Q[stack[i]][j] != 0)
               {
                  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;
               }
     }

     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;
     }