Cod sursa(job #656683)

Utilizator nautilusCohal Alexandru nautilus Data 4 ianuarie 2012 22:39:29
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include<fstream>
#include<cstring>
#include<vector>
using namespace std;
#define SMAX 10000010
#define CMAX 25
#define PUTERE 3
#define PRIM 666013

char s[SMAX];
int lungs,lungc;
int puteremax=1,cuvantc;
int pozitiicandidat;
vector<int> t[PRIM+10];

int search(int cuvant)
{
 int i,rest = cuvant % PRIM;
 for (i=0; i<(int)t[rest].size(); ++i)
	 if (t[rest][i] == cuvant)
		 return 1;
 return 0;
}

void insert(int cuvant)
{
 int rest = cuvant % PRIM;
 if ( !search(cuvant) )
	 t[rest].push_back(cuvant);
}

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();
	 cuvantc = 0;
	 for (i=0; i<(int)strlen(c); ++i)
		cuvantc = cuvantc * PUTERE + (c[i] - 'a');
	 insert(cuvantc);
	}
 lungc = (int)strlen(c);
}

void solve()
{
 int i,cuvants=0;
 for (i=0; i<lungc; ++i)
	{
	 cuvants = cuvants * PUTERE + (s[i] - 'a');
	 if (i > 0)
		puteremax = puteremax * PUTERE;
	}
 for (i=0; i<=lungs - lungc; ++i)
	{
	 if (i > 0)
		cuvants = (cuvants - (s[i-1] - 'a') * puteremax) * PUTERE + (s[i + lungc - 1] - 'a');
	 pozitiicandidat += search(cuvants);
	}
}

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

int main()
{
 read();
 solve();
 write();
 return 0;
}