Cod sursa(job #935476)

Utilizator DaNutZ2UuUUBB Bora Dan DaNutZ2UuU Data 3 aprilie 2013 15:57:32
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include<fstream>
#include<cstring>
#include<vector>
#define MOD 666013
using namespace std;
int n,m,sol;
char A[10000100],B[25];
vector <unsigned int> H[666013];

inline bool Search(unsigned int val)
{
	vector <unsigned int>::iterator it;
	int poz=val%MOD;
	for(it=H[poz].begin();it!=H[poz].end();it++)
		if(*it==val)
			return true;
	return false;
}

int main()
{
	int i;
	unsigned int rez,p;
	ifstream fin("abc2.in");
	fin>>(A+1);
	n=strlen(A+1);
	while(fin>>(B+1))
	{
		m=strlen(B+1);
		rez=0;
		for(i=1;i<=m;i++)
			rez=rez*3+(B[i]-'a');
		if(Search(rez)==false)
			H[rez%MOD].push_back(rez);
	}
	fin.close();

	if(n>=m)
	{
		rez=0;
		p=1;
		for(i=1;i<=m;i++)
		{
			rez=rez*3+(A[i]-'a');
			if(i<m)
				p=p*3;
		}
		if(Search(rez)==true)
			sol++;
		for(i=m+1;i<=n;i++)
		{
			rez=rez-p*(A[i-m]-'a');
			rez=rez*3+(A[i]-'a');
			if(Search(rez)==true)
				sol++;
		}
	}

	ofstream fout("abc2.out");
	fout<<sol<<"\n";
	fout.close();
	return 0;
}