Cod sursa(job #908905)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 10 martie 2013 10:52:54
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<fstream>
#include<cstring>
#include<set>
#define MOD 666013
using namespace std;
int n,m,sol;
char A[10000100],B[25];
set <unsigned int> S[666013];

inline bool Search(unsigned int val)
{
	set <unsigned int>::iterator it;
	it=S[val%MOD].lower_bound(val);
	if(it!=S[val%MOD].end() && *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');
		S[rez%MOD].insert(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;
}