Cod sursa(job #102327)

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