Cod sursa(job #1201608)

Utilizator vasile_pojogaPojoga Vasile vasile_pojoga Data 25 iunie 2014 15:26:00
Problema Potrivirea sirurilor Scor 26
Compilator cpp Status done
Runda Arhiva educationala Marime 2.24 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

string T,P;
unsigned int nrSol;
vector<int> sol;

void getMatches(string P, string T, unsigned int d, unsigned int q);
unsigned int pow(unsigned int d, unsigned int m, unsigned int q);
unsigned int getHash(string S, unsigned int d, unsigned int q);
unsigned int getNextHash(string T, unsigned int poz, unsigned int d, unsigned int q, unsigned int dM, unsigned int m, unsigned int prevH);
bool equal_string(string P, string T, unsigned int poz, unsigned int len);
void print();

int main()
{
	fin>>P>>T;
	getMatches(P,T,256,65521);
	print();
	return 0;
}

void getMatches(string P, string T, unsigned int d, unsigned int q)
{
	unsigned int m = P.length();
	unsigned int n = T.length();
	unsigned int dM = pow(d, m-1, q); //(d^(m-1))%q
	unsigned int h = getHash(P, d, q);
	unsigned int h1 = getHash(T.substr(0,m), d, q);
	nrSol = 0;
	sol.clear();
	for(unsigned int i=0; i<=n-m; i++)
	{
		if(h == h1 && equal_string(P,T,i,m))
		{
			nrSol++;
			sol.push_back(i);
		}
		h1 = getNextHash(T,i,d,q,dM,m,h1);
	}
}

unsigned int getHash(string S, unsigned int d, unsigned int q)
{
	unsigned int hash = S[0];
	for(unsigned int i=1; i<S.length(); i++)
	{
		hash = (hash * d + S[i]) % q;
	}
	return hash;
}

unsigned int getNextHash(string T, unsigned int poz, unsigned int d, unsigned int q, unsigned int dM, unsigned int m, unsigned int prevH)
{
	unsigned int hash = prevH;
	hash = (hash + q) - ((T[poz]*dM) % q); //removed previous
	hash = (hash * d) % q; //shifted with 1 position to left
	hash = (hash + T[poz + m]) % q; //added last value to hash
	return hash;
}

unsigned int pow(unsigned int d, unsigned int m, unsigned int q)
{
	unsigned int result = 1;
	for(unsigned int i=1; i<=m; i++)
	{
		result = (result * d) % q;
	}
	return result;
}

bool equal_string(string P, string T, unsigned int poz, unsigned int len)
{
	for(unsigned int i=0;i<len;i++)
	{
		if(P[i] != T[poz + i])
		{
			return false;
		}
	}
	return true;
}

void print()
{
	fout<<nrSol<<'\n';
	if(nrSol > 1000) nrSol = 1000;
	for(unsigned int i = 0; i < sol.size(); i++)
	{
		fout<<sol[i]<<' ';
	}
}