Pagini recente » Cod sursa (job #2442405) | Cod sursa (job #1077471) | Cod sursa (job #3180002) | Cod sursa (job #192258) | Cod sursa (job #102226)
Cod sursa(job #102226)
#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)
{
return ( *(long long*)a - *(long long*)b );
}
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;
}
int binary_search(int val)
{
int i, step;
for (step = 1; step < n; step <<= 1);
for (i = 0; step; step >>= 1)
if (i + step < n && a[i + step] <= val)
i += step;
if (a[i]==val)
return 1;
else
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+=binary_search(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+=binary_search(cod);
}
//puts(aux);
}
fprintf(out,"%d\n",t);
/*
for (i=0;i<=n;i++)
fputs(a[i],out);*/
fclose(out);
return 0;
}