Cod sursa(job #832479)

Utilizator lianaliana tucar liana Data 10 decembrie 2012 19:00:38
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb

#include <fstream>
#include <stdio.h>
#include <vector>
#include <cstring>
using namespace std;
#define p 666013
#define lgmax 10000005
#define lcmax 23
long rez, i, ls, lc;
unsigned long nr, p3, r, trei;
vector <unsigned long> ma[p+5];
vector <unsigned long> ::iterator it;
char s[lgmax], cuv[lcmax];
bool g, nc;

void citire()
{
	gets(s);	
	ls=strlen(s);
	while (gets(cuv))
	{
		if (nc==0)
			lc=strlen(cuv);
		nc=1;		nr=0;
		for (i=0;i<lc;i++)
			nr=nr*trei+cuv[i]-'a';
		r=nr%p;	g=0;
		for (it=ma[r].begin();it!=ma[r].end();it++)
			if ((*it)==nr)
			{	g=1;	break;	}
		if (!g)
			ma[r].push_back(nr);
	}
	
}

void rezolvare()
{
	p3=1;	nr=0;
	for (i=0;i<lc;i++)
	{
		if (i<lc-1)
			p3=p3*trei;
		nr=nr*trei+s[i]-'a';
	}
	r=nr%p;	g=0;
	for (it=ma[r].begin();it!=ma[r].end();it++)
		if ((*it)==nr)
		{	g=1;	break;	}
	rez+=g;
	for (i=lc;i<ls;i++)
	{
		nr=nr-(s[i-lc]-'a')*p3;
		nr=nr*trei+s[i]-'a';	
		r=nr%p;		g=0;
		for (it=ma[r].begin();it!=ma[r].end();it++)
			if ((*it)==nr)
			{	g=1;	break;	}
		rez+=g;
	}
}

int main()
{
	freopen("abc2.in","r",stdin);
	freopen("abc2.out","w",stdout);
	trei=3;
	citire();
	rezolvare();
	printf("%ld",rez);
	return 0;
}