Cod sursa(job #98613)

Utilizator Darth_NiculusIvan Nicolae Darth_Niculus Data 10 noiembrie 2007 15:07:55
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.51 kb
/* Ivan Nicolae - Bucuresti */
/* ABC2 - Happy Coding 2007 */
#include <stdio.h>
#include <string.h>

#define LMAX 10000001
#define NMAX 50001
#define CMAX 21
#define _fin  "abc2.in"
#define _fout "abc2.out"

char Text[LMAX],Cuv[NMAX][CMAX],Aux[CMAX];
int i,j,n,m;

void Quick(int li, int ls)
{
 int i=li, j=ls;
 char x[CMAX],y[CMAX];
 memcpy(x,Cuv[(li+ls)/2],sizeof(Cuv[(li+ls)/2]));
 while (i<=j)
      {
       while (strcmp(x,Cuv[i]) > 0) i++;
       while (strcmp(x,Cuv[j]) < 0) j--;
       if (i<=j)
         {
          memcpy(y,Cuv[i],sizeof(Cuv[i]));
          memcpy(Cuv[i],Cuv[j],sizeof(Cuv[j]));
          memcpy(Cuv[j],y,sizeof(y));
          i++; j--;
         }
      }
 if (i<ls) Quick(i,ls);
 if (li<j) Quick(li,j);
}

int BinSrch(int li, int ls, char X[])
{
 if (li>ls) return 0;
   else {
         int mij=(li+ls)/2;
         if (strcmp(Cuv[mij],X) == 0)
           return 1;
           else
         if (strcmp(Cuv[mij],X) > 0)
           return BinSrch(li,mij-1,X);
           else
         return BinSrch(mij+1,ls,X);
        }
}

int main()
{
 freopen(_fin,"r",stdin);
 freopen(_fout,"w",stdout);

 gets(Text); n=0;
 while (!feof(stdin))
      gets(Cuv[++n]); n--;
 m=strlen(Cuv[1]);

 Quick(1,n);

 int rez=0;
 for (i=0;i<=strlen(Text)-m;i++)
    {
     for (j=i;j<=i+m-1;j++)
        Aux[j-i]=Text[j];
//     printf("%s\n",Aux);
     if (BinSrch(1,n,Aux)) rez++;
    }

 printf("%d\n",rez);

 fclose(stdin);
 fclose(stdout);
 return 0;
}