Cod sursa(job #104798)

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

long n,m,p,q,l,i,p3l;
unsigned long lista[50002],lung[50002],sol,nr;
char sir[10000002],cuv[22];

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++;lung[p]=1;
        lista[p]=lista[i];
        while (i<q&&lista[i]==lista[i+1]){i++;lung[p]++;}
    }
    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+=lung[p];break;}}
          else if (nr<lista[m]){q=m-1;if (nr==lista[q]){sol+=lung[q];break;}}
               else {sol+=lung[m];break;}
    }
    for (i=l;i<strlen(sir)-l+1;i++){
        if (sir[i-l]=='b')nr-=p3l/3;
        else if (sir[i-l]=='c')nr-=2*p3l/3;
        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+=lung[p];break;}}
              else if (nr<lista[m]){q=m-1;if (nr==lista[q]){sol+=lung[q];break;}}
                   else {sol+=lung[m];break;}
        }
    }
    
    printf("%ld\n",sol);
    
    return 0;
}