Cod sursa(job #205370)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 31 august 2008 12:39:55
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.28 kb
# include <stdio.h>
# include <string.h>
# include <vector>

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=0,Sol=0,k=0;
char D[DMAX];
char s[LMAX];
vector <int> stack;

     void trie()
     {
         if (ok == 0)
           {
             len = strlen(s);
             ok = 1;
           }
         state = 1;
         for (i = 0; i < len; ++i)
           {
              if (Q[state][s[i]-'a'] != 0)
                state = Q[state][s[i]-'a'];
              else
                {
                   Q[state][s[i]-'a'] = ++N;   
                   state = N;
                }
           }
         Ac[N] = 1;
     }
     
     void failure()
     {
         int sf = 0,u,i; 
         for (i = 0; i < 3; ++i)
           if (Q[1][i] != 1)
             {
                stack.push_back(Q[1][i]);
                sf++;
                Fail[Q[1][i]] = 1;
             }
         
         for (i = 0; i < sf; ++i)
           for (j = 0; j < 3; ++j)
             if (Q[stack[i]][j] != 0)
               {
                  stack.push_back(Q[stack[i]][j]);
                  sf++;
                  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);
         
         gets(D);
         while (!feof(stdin))
           {
               gets(s);
               trie();
           }
         for (i = 0; i < 3; ++i)
           if (Q[1][i] == 0) Q[1][i] = 1;
           
         failure();
         
         len = strlen(D);
         state = 1;
         for (i = 0; i < len; ++i)
           {
              while (Q[state][D[i]-'a'] == 0)
                state = Fail[state];
              state = Q[state][D[i]-'a'];
              Sol += Ac[state];
           }
         
         printf("%d",Sol);
         
         return 0;
     }