Cod sursa(job #832462)

Utilizator lianaliana tucar liana Data 10 decembrie 2012 18:35:30
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
#define p 1000003
#define lgmax 666013
#define lcmax 50005
long rez, i, ls, lc;
long long nr, p3, r, trei;
vector <long long> ma[p+5];
vector <long long> ::iterator it;
char s[lgmax], cuv[lcmax];
bool g;

void citire()
{
	
	
}

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()
{
	ifstream fin("abc2.in");
	ofstream fout("abc2.out");
	trei=3;
	citire();
	fin >> s;	ls=strlen(s);
	while ((fin>>cuv))
	{
		lc=strlen(cuv);
		if (lc==0)
			break;
		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);
	}
	rezolvare();
	fout << rez;
	fin.close();
	fout.close();
	return 0;
}