Cod sursa(job #656741)

Utilizator nautilusCohal Alexandru nautilus Data 5 ianuarie 2012 00:37:57
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include<fstream>
#include<vector>
#include<cstring>
using namespace std;
#define SMAX 10000010
#define CMAX 25
#define PRIM 90907
#define PUTERE 3

char s[SMAX],cuv[CMAX];
int lungs,lungcuv;
vector<unsigned int> t[PRIM + 10];
unsigned int puteremax=1,pozcandidat;

void memorare()
{
 unsigned int rest,valoarecuv=0;
 int i,ok=0;
 for (i=0; i<(int)strlen(cuv); ++i)
	 valoarecuv = valoarecuv * PUTERE + (cuv[i] - 'a');

 rest = valoarecuv % PRIM;
 for (i=0; i<(int)t[rest].size(); ++i)
	 if (t[rest][i] == valoarecuv)
		{
		 ok = 1; 
		 break;
		}
 if (ok == 0)
	t[rest].push_back(valoarecuv);
}

void read()
{
 ifstream fin("abc2.in");
 fin.get(s, SMAX); fin.get();
 lungs = strlen(s);
 while ( !fin.eof() )
	{
	 fin.get(cuv, CMAX); fin.get();
	 memorare();
	}
 lungcuv = strlen(cuv);
}

void solve()
{
 int i,j;
 unsigned int rest,valoares=0;
 for (i=0; i<lungcuv; ++i)
	{
	 valoares = valoares * PUTERE + (s[i] - 'a');
	 if (i > 0)
		 puteremax *= PUTERE;
	}

 for (i=0; i<=lungs - lungcuv; ++i)
	{
	 if (i != 0)
		 valoares = (valoares - ((s[i - 1] - 'a') * puteremax)) * PUTERE + (s[i + lungcuv - 1] - 'a');
	 rest = valoares % PRIM;
	 for (j=0; j<(int)t[rest].size(); ++j)
		 if (t[rest][j] == valoares)
			{
			 pozcandidat++;
			 break;
			}
	}
}

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

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