Cod sursa(job #832476)

Utilizator lianaliana tucar liana Data 10 decembrie 2012 18:57:23
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include<stdio.h>
#include<cstring>
#include<vector>
using namespace std;
#define p 666013
#define lgmax 10000005
#define lcmax 25
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;

void citire()
{
	scanf("%s",&s);	ls=strlen(s);
	while (scanf("%s",&cuv)==1)
	{
		lc=strlen(cuv);
		if (lc==0)
			break;
		nr=0;
		for (i=0;i<lc;i++)
			nr=nr*trei+cuv[i]-'a';
		r=nr%p;	
		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;
	}
	printf("%ld",rez);
}

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