Cod sursa(job #99606)

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

#define lmax 10000005
#define wmax 25
#define usi char
#define hmax 10020003
#define hmax1 5900007
#define baza 3
#define baza1 4
#define LL long long

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

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; hs1 = 0; l = strlen(s1);
		for(i = 0; i < (int)strlen(s1); i++) 
		{
			hs = (LL)hs * baza + (LL)(s1[i] - 'a');
			hs1 = (LL)hs1 * baza1 + (LL)(s1[i] - 'a');
		}
		a[hs % hmax] = 1;
		b[hs1 % hmax1] = 1;
	}
	hs = 0, hs1 = 0, tbaza = 1, tbaza1 = 1, n = strlen(s);
	for(i = 0; i < l - 1; i++)
	{
		crt++; tbaza *= (LL)baza; tbaza1 *= (LL)baza1;
		hs = (LL)hs * baza + (LL)(s[i] - 'a');
		hs1 = (LL)hs1 * baza1 + (LL)(s[i] - 'a');
	}
	
	for(i = l - 1; i < n; i++)
	{
		hs = (LL)hs * baza + (LL)(s[i] - 'a');
		hs1 = (LL)hs1 * baza1 + (LL)(s[i] - 'a');
		if(a[hs % hmax] && b[hs1 % hmax1]) tot++;
		if(s[i - l + 1] - 'a' != 0) {
			hs -= (LL)(s[i - l + 1] - 'a') * tbaza;
			hs1 -= (LL)(s[i - l  + 1] - 'a') * tbaza1;
		}
	}

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

	return 0;
}