Cod sursa(job #99701)

Utilizator stef2nStefan Istrate stef2n Data 11 noiembrie 2007 15:11:25
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.1 kb
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

#define LMAX 10000005
#define MOD 666013

int L; char text[LMAX];
int l;
vector <unsigned int> H[MOD+5];
int cnt=0;

void insert_hash(unsigned int x)
{
	int key=x%MOD;
	for(vector <unsigned int>::iterator it=H[key].begin(); it!=H[key].end(); ++it)
		if(*it==x)
			return;
	H[key].push_back(x);
}

int find_hash(unsigned int x)
{
	int key=x%MOD;
	for(vector <unsigned int>::iterator it=H[key].begin(); it!=H[key].end(); ++it)
		if(*it==x)
			return 1;
	return 0;
}

void read_data()
{
	char secv[25];
	fgets(text,LMAX,stdin);
	L=strlen(text)-1;
	fgets(secv,25,stdin);
	l=strlen(secv)-1;
	do
	{
		unsigned int nr=0;
		for(int i=0; i<l; ++i)
			nr=nr*3+(secv[i]-'a');
		insert_hash(nr);
	}
	while(fgets(secv,25,stdin));
}

void solve()
{
	unsigned int nr=0, p3=1;
	for(int i=0; i<l-1; ++i)
	{
		nr=nr*3+(text[i]-'a');
		p3*=3;
	}
	for(int i=l-1; i<L; ++i)
	{
		nr=(nr%p3)*3+(text[i]-'a');
		cnt+=find_hash(nr);
	}
}


int main()
{
	freopen("abc2.in","r",stdin);
	freopen("abc2.out","w",stdout);
	read_data();
	solve();
	printf("%d\n",cnt);
	return 0;
}