Cod sursa(job #1379119)

Utilizator NistorSergiuNistor Sergiu NistorSergiu Data 6 martie 2015 16:24:47
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include<fstream>
#include<vector>
#include<cstring>

#define LTMAX 10000001
#define key 1299827

using namespace std;


vector <int> ha[key];

vector <int> :: iterator find(int value)
{
	int list=value%key;
	vector <int> :: iterator it;
	for(it=ha[list].begin(); it!=ha[list].end(); it++)
		if(*it==value)
			return it;
	return ha[list].end();
}

void insert(int value)
{
	if(find(value)==ha[value%key].end())
		ha[value%key].push_back(value);
}

bool exists(int value)
{
	if(find(value)==ha[value%key].end())
		return 0;
	return 1;
}

char text[LTMAX];
char word[21];

int get_number(char str[])
{
	int i;
	int nr=0;
	int l=strlen(str);
	for(i=0; i<l; i++)
		nr=nr*3+str[i]-'a';
	return nr;
}

int main()
{
	int lword;
	int ltext;
	int i;
	int nr=0;
	int total=0;
	int p3=1;
	ifstream f("abc2.in");
	f>>text;
	f>>word;
	lword=strlen(word);
	insert(get_number(word));
	while(f>>word)
		insert(get_number(word));
	f.close();
	ofstream g("abc2.out");
	ltext=strlen(text);
	if(lword>ltext)
	{
		g<<"0\n";
		g.close();
		return 0;
	}
	for(i=0; i<lword; i++)
	{
		p3*=3;
		nr=nr*3+text[i]-'a';
	}
	p3/=3;
	if(exists(nr))
		total++;
	for(i=lword; i<ltext;i++)
	{
		nr=(nr-p3*(text[i-lword]-'a'))*3+text[i]-'a';
		if(exists(nr))
			total++;
	}
	g<<total<<'\n';
	g.close();
	return 0;
}