Pagini recente » Clasamentul arhivei de probleme | Cod sursa (job #2991102) | Cod sursa (job #904462) | Cod sursa (job #655450) | Cod sursa (job #100510)
Cod sursa(job #100510)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char s[10000002];
int a[50000];
int n,m;
int compar(const void *a,const void *b)
{
char *aa=(char*)a,*bb=(char*)b;
return strcmp(aa,bb);
}
int cauta(int 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)
{
int 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,exp,cod=0,exp_2,i;
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)
t+=cauta(cod);
else
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;
}