Pagini recente » Cod sursa (job #1094396) | Cod sursa (job #1714631) | Cod sursa (job #1586535) | Cod sursa (job #143489) | Cod sursa (job #104853)
Cod sursa(job #104853)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
long n,m,p,q,l,i,p3l,lung;
unsigned long lista[50002],sol,nr;
char sir[10000005],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++;
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);
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-=2*p3l/3;
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;
}