Cod sursa(job #102220)

Utilizator hadesgamesTache Alexandru hadesgames Data 14 noiembrie 2007 08:54:11
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.23 kb
#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;
}
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;
}