Cod sursa(job #102493)

Utilizator peanutzAndrei Homorodean peanutz Data 14 noiembrie 2007 14:25:50
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.14 kb
#include <stdio.h>
#include <vector>
#include <set>

using namespace std;

#define pb push_back
#define MOD 301001
#define NMAX 10000010

inline int f(int n)
{
	if(n == 0) return 1;
	int p = 1;
	for(int i = 1; i < n; ++i)
		p *= 3;
	return p;
}

char s[NMAX], c[21];
int n;
int res;
set<int> h[MOD];

void read()
{
	scanf("%s", c);
	if(!n)
		n = strlen(c);
	int x = 0;
	for(int i = 0; i < n; ++i)
		x = x*3 + (c[i]-'a');
	h[x % MOD].insert(x);
    //printf("x %d\n", x);
}

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

	scanf("%s", s);
	while(!feof(stdin))
		read();
	int t = 0, p = f(n);
	for(int i = 0; i < n; ++i)
		t = t*3 + (s[i]-'a');

	set<int> :: iterator it;
	int until = strlen(s)-n, aux;
	for(int i = 0; i <= until; ++i)
	{
        aux = t % MOD;//  printf("%d\n", t);
		for(it = h[aux].begin(); it != h[aux].end(); ++it)
			if(*it == t)
				++res;//, printf("%d %d\n", *it, t);
        t = t - p*(s[i]-'a');
        t = t*3 + (s[i+n]-'a');
	}
	printf("%d\n", res);
	return 0;
}