Pagini recente » Cod sursa (job #1699450) | Cod sursa (job #72573) | Cod sursa (job #1204328) | Cod sursa (job #2601715) | Cod sursa (job #100545)
Cod sursa(job #100545)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char s[10000002];
long long a[50000];
int n,m;
int compar(const void *a,const void *b)
{
long long *aa=(long long*)a,*bb=(long long*)b;
if (*aa<*bb)
return -1;
if (*bb>*aa)
return 1;
return 0;
}
int cauta(long long x)
{
int p=0,u=n-1,m;
while(p<u){
m=(p+u)/2;
if(x<=a[m])
u=m;
else
p=m+1;
}
if(a[p]==x)
return 1;
return 0;
}
void codificare(char * x,int n)
{
long long exp,i;
exp=1;
a[n]=0;
for (i=m-1;i>=0;i--)
{
a[n]+=exp*(x[i]-'a');
exp*=3;
}
}
int main()
{
int t=0,i;
long long exp,cod=0,exp_2;
char c[25];
FILE *in,*out;
in=fopen("abc2.in","r");
out=fopen("abc2.out","w");
fscanf(in,"%s\n",s);
m=-1;
while (fscanf(in,"%s\n",c)!=EOF)
{
if (m==-1)
m=strlen(c);
codificare(c,n++);
}
fclose(in);
qsort(a,n,sizeof(a[0]),compar);
exp=1;
cod=0;
for (i=1;i<m;i++)
exp*=3;
exp_2=exp;
for(char*p=s;*(p);++p)
{
if (p-s+1==m+1)
t+=cauta(cod);
if (p-s+1<=m)
{
cod+=(p[0]-'a')*exp_2;
exp_2/=3;
}
else
{
cod%=exp;
cod=cod*3+(p[0]-'a');
t+=cauta(cod);
}
//puts(aux);
}
fprintf(out,"%d\n",t);
/*
for (i=0;i<=n;i++)
fputs(a[i],out);*/
fclose(out);
return 0;
}