Cod sursa(job #346350)

Utilizator oganeaGanea Octavian oganea Data 7 septembrie 2009 15:31:49
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

#define hash 7000001

int a[hash];

int cod(char *aux, int len){
	int e = 1 , cod = 0;
	while (len >0  ){
		cod += (e*(int)(*aux - 'a'));
		cod = cod %hash;
		//cod += ((int)(*aux - 'a'));
		e*= 3;
		aux ++;
		len --;
	}
	return cod %hash;
}


int main (){
	int i;
	freopen ("abc2.in","r",stdin);
	freopen ("abc2.out","w",stdout);
	char *s = (char *)malloc (10000002*sizeof(char));
	char *aux = (char *)malloc (21*sizeof(char));

	scanf("%s",s);

	for(int i=0; i<hash; i++){ a[i]=0;}
	i=1;
	memset(aux,0,21);
	int len;
	while(scanf("%s",aux) && i <= 50000){
		//
		i++;
		len = strlen(aux);
		///printf("%s\n",aux);
		a[cod(aux , strlen(aux))]=1;
//		printf("codul de la %s:%d\n",aux,cod(aux, strlen(aux)));
		memset(aux,0,21);
	}
	
	int rez = 0;
	
	
	int indice = cod(s,len);
	s += len;
	rez += a[indice];
	int putere = 1;
	for(i=1 ; i < len; i++)
			putere *= 3;

	while(*s){
		indice -=  (*(s-len)-'a');
		indice = indice / 3;
		indice +=  (*s - 'a')*putere;
		indice = indice %hash;
		rez += a[indice];
//		printf("poz: %s %d\n", s+1 -len, indice);
//		if(a[indice])
//			printf("%d\n",indice); 
		s++;
	}

	printf("%d\n", rez);
//	while(1){}
	return 0;
}