Pagini recente » Cod sursa (job #1928890) | Cod sursa (job #2351878) | Cod sursa (job #1777502) | Cod sursa (job #1587532) | Cod sursa (job #102625)
Cod sursa(job #102625)
#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;
}