Cod sursa(job #609371)

Utilizator ilie.danilaIlie Teodor Danila ilie.danila Data 20 august 2011 23:34:17
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <math.h>

using namespace std;

#define base_prime 73
#define big_prime 1987

//data section

char sirA[2000001], sirB[2000001];
int n, m;

int aparitii[1002], nAparitii;

long long hashB = 0, hashA = 0;

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

	fin.getline(sirB, 2000001);
	fin.getline(sirA, 2000001);

	n = strlen(sirA);
	m = strlen(sirB);

	//get hash B 
	for( int i = 0; i < m; i++ )
	{
		hashB = int (hashB + sirB[i] * pow( double( base_prime ), double( m - i - 1 ) ) ) % big_prime;
	}

	//get hash A prev

	for( int i = 0; i < m; i++ )
	{
		hashA = int (hashA + sirA[i] * pow( double( base_prime ), double( m - i - 1 ) ) ) % big_prime;
	}

	if( hashA == hashB )
	{
		nAparitii = 1;
		aparitii[1] = 0;
	}

	for( int i = 1; i <= n - m; i++ )
	{
		hashA = hashA + big_prime * pow( base_prime, double( m - 1 ) );
		hashA = hashA - sirA[i-1] * pow( base_prime, double( m - 1 ) );
		hashA = hashA * base_prime;
		hashA = hashA + sirA[i + m - 1];
		hashA = hashA % big_prime;

		if( hashA == hashB && nAparitii < 1000 )
		{
			nAparitii++;
			aparitii[nAparitii] = i;
		}
	}

	fout << nAparitii << "\n";

	for( int i = 1; i <= nAparitii; i++)
	{
		fout << aparitii[i] << " ";
	}
	fout << "\n";

	return 0;
}