Cod sursa(job #656134)

Utilizator nautilusCohal Alexandru nautilus Data 3 ianuarie 2012 23:03:36
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include<fstream>
#include<cstring>
#include<algorithm>
using namespace std;
#define SMAX 10000010
#define NMAX 50010
#define CMAX 25
#define PUTERE 101
#define PRIM1 100003
#define PRIM2 100019

typedef struct hashh
{
 int unu,doi;
} hashh;

int n=-1;
hashh hashc[NMAX];
char s[SMAX];
int lungs,lungc;
int hashscurentunu,hashscurentdoi;
int pozitiicandidat;

bool comp (hashh a, hashh b)
{
 if (a.unu = b.unu)
	return a.doi < b.doi; else
	return a.unu < b.unu;
}

void cauta(int st, int dr)
{
 int mijl = (st + dr) / 2;
 if (st <= dr)
	{
	 if (hashscurentunu == hashc[mijl].unu && hashscurentdoi == hashc[mijl].doi)
		 pozitiicandidat++; else
		 if ((hashscurentunu == hashc[mijl].unu && hashscurentdoi < hashc[mijl].doi) || hashscurentunu < hashc[mijl].unu)
			 cauta(st, mijl-1); else
			 cauta(mijl+1, dr);
	}
}

void solve()
{
 int i,puteremax1=1,puteremax2=1;
 for (i=0; i<lungc; ++i)
	{
	 hashscurentunu = (hashscurentunu * PUTERE + s[i]) % PRIM1;
	 hashscurentdoi = (hashscurentdoi * PUTERE + s[i]) % PRIM2;
	 if (i > 0)
		{
		 puteremax1 = (puteremax1 * PUTERE) % PRIM1;
		 puteremax2 = (puteremax2 * PUTERE) % PRIM2;
		}
	}
 for (i=0; i<=lungs - lungc; ++i)
	{
	 if (i > 0)
		{
		 hashscurentunu = ((hashscurentunu - (s[i-1] * puteremax1) % PRIM1 + PRIM1) * PUTERE + s[i + lungc - 1]) % PRIM1;
		 hashscurentdoi = ((hashscurentdoi - (s[i-1] * puteremax2) % PRIM2 + PRIM2) * PUTERE + s[i + lungc - 1]) % PRIM2;
		}
	 cauta(0, n);
	}
}

void read()
{
 int i;
 char c[CMAX];
 ifstream fin("abc2.in");
 fin.get(s, SMAX); fin.get();
 lungs = (int)strlen(s);
 while ( !fin.eof() )
	{
	 fin.get(c, CMAX); fin.get();
	 ++n;
	 for (i=0; i<(int)strlen(c); ++i)
		{
		 hashc[n].unu = (hashc[n].unu * PUTERE + c[i]) % PRIM1;
		 hashc[n].doi = (hashc[n].doi * PUTERE + c[i]) % PRIM2;
		}
	}
 lungc = (int)strlen(c);
}

void write()
{
 ofstream fout("abc2.out");
 fout<<pozitiicandidat<<'\n';
 fout.close();
}

int main()
{
 read();
 sort(hashc, hashc+n+1, comp);
 solve();
 write();
 return 0;
}