Cod sursa(job #99589)

Utilizator alextheroTandrau Alexandru alexthero Data 11 noiembrie 2007 13:09:21
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 0.83 kb
#include <stdio.h>
#include <string.h>

#define lmax 10000005
#define wmax 25
#define usi char
#define hmax 10020003
#define baza 3
#define LL long long

char s[lmax], s1[wmax], n;
int tot, i, l, crt = 0, tbaza;
LL hs;
usi a[hmax];

int main()
{
	freopen("abc2.in", "r", stdin);
	freopen("abc2.out", "w", stdout);

	scanf("%s\n", s); 
	while(!feof(stdin))
	{
		scanf("%s\n", s1);
		hs = 0; l = strlen(s1);
		for(i = 0; i < (int)strlen(s1); i++)
			hs = (LL)hs * baza + (LL)(s1[i] - 'a');
		a[hs % hmax] = 1;
	}
	hs = 0; tbaza = 1, n = strlen(s);
	for(i = 0; i < l - 1; i++)
	{
		crt++; tbaza *= baza;
		hs = (LL)hs * baza + (LL)(s[i] - 'a');
	}
	
	for(i = l - 1; i < n; i++)
	{
		hs = (LL)hs * baza + (LL)(s[i] - 'a');
		if(a[hs % hmax]) tot++;
		if(s[i - l + 1] - 'a' != 0) hs -= (LL)(s[i - l + 1] - 'a') * tbaza;
	}

	printf("%d\n", tot);

	return 0;
}