Cod sursa(job #102625)

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

long n,m,p,q,l,i,nr,p3l;
unsigned long lista[50002],lung[50002],sol;
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=0;
    while (strcmp(cuv,"")){
          q++;lista[q]=1;
          for (i=0;i<l;i++)
              lista[q]=lista[q]*3+cuv[i]-'a';
          strcpy(cuv,"");
          scanf("%s",cuv);
    }
    qsort(lista,q+1,sizeof(unsigned long),comp);
    p=0;
    for (i=1;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=1;
    for (i=0;i<l;i++){nr*=3;nr+=sir[i]-'a';}
    //cautarea binara
    p=1;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++){
        nr-=p3l;
        if (sir[i-l]=='a')nr+=p3l/3;
        else if (sir[i-l]=='c')nr-=p3l/3;
        nr*=3;
        nr+=sir[i]-'a';
        //cautarea binara
        p=1;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;
}