Cod sursa(job #253341)

Utilizator 630r63Ilinca George Mihai 630r63 Data 5 februarie 2009 18:07:32
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
 #include<stdio.h>  
 #include<string.h>  
 #include<stdlib.h>  
 #include<algorithm>  
 #define N 50007  
   
 int v[30],enc[N];  
 char s[200*N],dict[30];  
 int n,m,k,val,nr;  
   
 int caut_bin(int *q,int l,int c){  
     int op,r=1;  
     for(op=1;op<l;op<<=1);  
     for(;op;op>>=1)  
         if((r+op<=l)&&(q[r+op]<=c))  
             r+=op;  
         if(q[r]==c)  
             return 1;  
         return 0;  
 }  
   
 void calc(){  
     int i;  
     for(i=1;i<=n-m+1;++i){  
         val-=v[m-1]*(s[i-1]-'s');  
         val=val*3+s[i+m-1]-'s';  
         if(caut_bin(enc,k,val))  
             nr++;  
     }  
     printf("%d\n",nr);  
 }  
   
 int add(int m,char *s){  
     int i,p=0;  
     for(i=0;i<m;++i)  
         p+=v[m-i-1]*(s[i]-'s');  
     return p;  
 }  
   
 void citire(){  
     int i;  
     scanf("%s",s);  
     scanf("%s",dict);  
     n=strlen(s);  
     m=strlen(dict);  
     v[0]=1;  
     for(i=1;i<=m;++i)  
         v[i]=v[i-1]*3;  
     enc[1]=add(m,dict);  
     k=1;  
     while(scanf("%s",dict)!=EOF){  
         enc[++k]=add(m,dict);  
     }  
 }  
   
 int main(){  
     freopen("abc2.in","r",stdin);  
     freopen("abc2.out","w",stdout);  
     citire();  
     std::sort(enc+1,enc+1+k);  
     val=add(m,s);  
     if(caut_bin(enc,k,val))  
         nr=1;  
     calc();  
     fclose(stdin);  
     fclose(stdout);  
     return 0;  
}