Cod sursa(job #108326)

Utilizator C_OvidiuCotletz Ovidiu C_Ovidiu Data 22 noiembrie 2007 10:39:37
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include<stdio.h>
#include<string.h>
#include<fstream.h>
#define NM 10000002
#define lmax 22
#define nmax 50002
#define nodmax 1000005
char ter[nodmax],sir[NM],c[nmax][lmax];
long f[nodmax][3],pref[nodmax],sol,N,l,n;


void read()
{long i;

 freopen("abc2.in","r",stdin);
 scanf("%s",&sir);
 n=strlen(sir);
 i=1;
 while(!feof(stdin))
   scanf("%s",&c[i++]);
 N=i-2;
 l=strlen(c[1]);
 }


void make_trie()
{long  val,nr,i,x,j,k,v[nodmax],vv[lmax],vvv[lmax],t[nodmax];
 memset(t,0,sizeof(t));
 memset(v,0,sizeof(v));

 nr=0;

 for(i=1;i<=N;i++)
   {x=0;
    for(j=0;j<l;j++)
      {
      val=c[i][j]-'a';
      if(!f[x][val])
       {
       f[x][val]=++nr;
       t[nr]=x;
       v[nr]=val;
       }
      x=f[x][val];
      }
   ter[nr]=1;
   }

 for(i=1,x=0;i<=nr;i++)
  if(t[i])
   {
   val=v[i];
   x=pref[t[i]];
   while(!f[x][val]&&x)
     x=pref[x];
   x=f[x][val];
   pref[i]=x;
   }
  else
   pref[i]=0;
 }


void solve()
{long i,x,val;


 x=0;
 sol=0;
 for(i=0;i<n;i++)
  {
   val=sir[i]-'a';
   while(!f[x][val]&&x)
     x=pref[x];
   //if(!x&&f[0][val])
   //  x=f[0][val];
   x=f[x][val];
   if(ter[x])
     sol++;
  }


}

void print()
{
 freopen("abc2.out","w",stdout);
 printf("%ld",sol);
 fclose(stdout);
 }






















int main()
{
 read();
 make_trie();
 solve();
 print();

 return 0;
 }