Cod sursa(job #104891)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 16 noiembrie 2007 19:39:37
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.77 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long n,m,p,q,l,i,lung;
unsigned long lista[50003],p3l,sol=0,nr;
char sir[10000005],cuv[23];

int comp(const void *n1,const void *n2){
    return *((long*)n1)-*((long*)n2);
}

int main(){
    freopen("abc2.in","r",stdin);
    freopen("abc2.out","w",stdout);
    
    scanf ("%s\n",sir);
    
    scanf ("%s\n",cuv);
    l=strlen(cuv);
    p3l=1;
    for (i=1;i<=l;i++)p3l*=3;
    q=-1;
    while (strcmp(cuv,"")){
          q++;lista[q]=0;
          for (i=0;i<l;i++)
              lista[q]=lista[q]*3+cuv[i]-'a';
          strcpy(cuv,"");
          scanf("%s",cuv);
    }
    qsort(lista,q,sizeof(unsigned long),comp);
    p=-1;
    for (i=0;i<=q;i++){
        p++;
        lista[p]=lista[i];
        while (i<q&&lista[i]==lista[i+1])i++;
    }
    n=p;
    nr=0;
    for (i=0;i<l;i++){nr*=3;nr+=sir[i]-'a';}
    //cautarea binara
    p=0;q=n;
    while (p<=q){
          m=(p+q)/2;
          if (nr>lista[m]){p=m+1;if (nr==lista[p]){sol++;break;}}
          else if (nr<lista[m]){q=m-1;if (nr==lista[q]){sol++;break;}}
               else {sol++;break;}
    }
    lung=(long)strlen(sir);
    //printf("%ld\n",lung);
    for (i=l;i<lung;i++){
        //nr=3*(nr-(sir[i-l]-'a')*p3l)+sir[i]-'a';
        if (sir[i-l]=='b')nr-=p3l/3;
        else if (sir[i-l]=='c')nr-=p3l/3*2;
        nr*=3;
        nr+=sir[i]-'a';
        //cautarea binara
        p=0;q=n;
        while (p<=q){
              m=(p+q)/2;
              p=m+1;
              if (nr>lista[m]){p=m+1;if (nr==lista[p]){sol++;break;}}
              else if (nr<lista[m]){q=m-1;if (nr==lista[q]){sol++;break;}}
                   else {sol++;break;}
        }
        
    }
    
    printf("%ld\n",sol);
    
    return 0;
}