Cod sursa(job #346318)

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

#define hash 200000001

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.txt","r+",stdin);
	freopen ("abc2.out","w",stdout);
	char *s = (char *)malloc (10000002);
	char *aux = (char *)malloc (21);

	scanf("%s",s);

	for(int i=0; i<hash; i++){ a[i]=0;}
	i=1;
	
	while(scanf("%s",aux) && i < 50000){
		//
		i++;
		///printf("%s\n",aux);
		a[cod(aux , strlen(aux))]=1;
//		printf("codul de la %s:%d\n",aux,cod(aux, strlen(aux)));
	}
	
	int rez = 0;
	int len = strlen(aux);
	
	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];
//		if(a[indice])
//			printf("%d\n",indice); 
		s++;
	}

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