Cod sursa(job #1379065)

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

#define LTMAX 10000001

using namespace std;

struct Hash
{
	vector < vector<int> > ha;
	int key;

	Hash()
	{
		int i;
		key=700001;
		vector <int> v;
		for(i=0; i<key; i++)
			ha.push_back(v);
	}

	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*10+str[i]-'a';
	return nr;
}

int main()
{
	Hash h;
	int lword;
	int ltext;
	int i;
	int nr=0;
	int total=0;
	int p10=1;
	ifstream f("abc2.in");
	f>>text;
	f>>word;
	lword=strlen(word);
	h.insert(get_number(word));
	while(f>>word)
		h.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++)
	{
		p10*=10;
		nr=nr*10+text[i]-'a';
	}
	p10/=10;
	if(h.exists(nr))
		total++;
	for(i=lword; i<ltext;i++)
	{
		nr=(nr-p10*(text[i-lword]-'a'))*10+text[i]-'a';
		if(h.exists(nr))
			total++;
	}
	g<<total<<'\n';
	g.close();
	return 0;
}