Cod sursa(job #1039228)

Utilizator cat_red20Vasile Ioana cat_red20 Data 22 noiembrie 2013 18:19:17
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include<fstream>
#include<algorithm>
#include<cstring>
#include<vector>
#define MOD 666013

using namespace std;
int l,lung,k,u,poz,sol;
unsigned int p3,val,v[50001];
char s[10000001],sir[21];
ifstream fin("abc2.in");
ofstream fout("abc2.out");

unsigned int genereazaHash(char s[],int l)
{
	unsigned int h=0;
	for(int i=0;i<l;i++)
	{
		h=h*3+s[i]-'a';
	}
    return h;
}

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

void putere3()
{
	p3=1;
	for(int i=1;i<lung;i++)
	{
		p3*=3;
	}
}

int cauta(unsigned int val)
{
    int p=1,u=k,m;
    while(p<=u)
    {
        m=(p+u)/2;
        if(v[m]==val)
            return 1;
        if(v[m]<val)
            p=m+1;
        else
            u=m-1;
    }
    return 0;
}

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