Cod sursa(job #1036279)

Utilizator cat_red20Vasile Ioana cat_red20 Data 19 noiembrie 2013 09:37:52
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include<fstream>
#include<algorithm>
#include<cstring>
#define MOD1 666013
#define MOD2 100021
using namespace std;
int l,lung,k,u,poz,sol,p3,p3m1,p3m2;
char s[10000001],sir[21];
struct code
{
	int h1,h2;
};
code h[50001],val;

ifstream fin("abc2.in");
ofstream fout("abc2.out");

int cmp(code a,code b)
{
	return a.h1<b.h1;
}

void genereazaHash(char s[],int l,code &h)
{
	for(int i=0;i<l;i++)
	{
		h.h1=(h.h1*3+s[i]-'a')%MOD1;
		h.h2=(h.h2*3+s[i]-'a')%MOD2;
	}
}

void prelucareDictionar()
{
	fin.getline(sir,21);
	lung=strlen(sir);
	do
	{
		genereazaHash(sir,lung,h[++k]);
	}while(fin.getline(sir,21));
	sort(h+1,h+k+1,cmp);
	u=1;;

}

void putere3()
{
	p3=1;
	for(int i=1;i<lung;i++)
	{
		p3*=3;
	}
	p3m1=p3%MOD1;
	p3m2=p3%MOD2;
}

int cauta(code val)
{
	int st=1,dr=k,m;
	while(st<=dr)
	{
		m=(st+dr)/2;
		if(h[m].h1==val.h1)
		{
			if(h[m].h2==val.h2)
				return 1;
			return 0;
		}

		if(h[m].h1<val.h1)
		{
			st=m+1;
		}
		else
			dr=m-1;
	}
	return 0;
}

int main()
{
	fin.getline(s,10000001);
	l=strlen(s);
	prelucareDictionar();
	if(l<lung)
	{
		fout<<0;
		return 0;
	}
	putere3();
	genereazaHash(s,lung,val);
	sol+=cauta(val);
	for(int i=lung;i<l;i++)
	{
		val.h1-=((s[i-lung]-'a')*p3m1 )%MOD1;
		if(val.h1<0)
            val.h1+=MOD1;
		val.h1=val.h1*3+s[i]-'a';
		while(val.h1>MOD1)
		val.h1-=MOD1;

		val.h2-=((s[i-lung]-'a')*p3m2)%MOD2;
		if(val.h2<0)
            val.h2+=MOD2;
		val.h2=val.h2*3+s[i]-'a';
        while(val.h2>MOD2)
        val.h2-=MOD2;

		sol+=cauta(val);
	}
	fout<<sol;
	return 0;
}