Cod sursa(job #656153)

Utilizator nautilusCohal Alexandru nautilus Data 4 ianuarie 2012 00:17:14
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 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];

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

void insert()
{
 if (search(cuvantc) == 0)
	 t[cuvantc % PRIM].push_back(cuvantc);
}

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();
	}
 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;
}