Cod sursa(job #2211269)

Utilizator AlexDabuDabu Alexandru AlexDabu Data 9 iunie 2018 18:15:35
Problema Potrivirea sirurilor Scor 86
Compilator cpp Status done
Runda Arhiva educationala Marime 1.85 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string>

#define P 73
#define MOD1 100007
#define MOD2 100021

using namespace std;

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

string A, B;
int numberOfMatches = 0;
vector <int> indexListOfMatches;

void Read(void)
{
	fin >> A >> B;
}

int Hash(int charA, int charB)
{
	int base = 256;
	int primeModulus = 101;
	int hashValue;
	hashValue = ((charA % primeModulus) * base + (int)charB) % primeModulus;
	return hashValue;
}

void Match(void)
{
	int lengthA, lengthB;
	lengthA = A.size();
	lengthB = B.size();

	if (lengthA > lengthB)
	{
		fout << "0\n";
		return;
	}

	int P1 = 1, P2 = 1;
	int hashA1 = 0, hashA2 = 0;
	for (int i = 0; i < lengthA; i++)
	{
		hashA1 = (hashA1 * P + A[i]) % MOD1;
		hashA2 = (hashA2 * P + A[i]) % MOD2;

		if (i != 0)
		{
			P1 = (P1 * P) % MOD1;
			P2 = (P2 * P) % MOD2;
		}
	}

	int hash1 = 0, hash2 = 0;
	for (int i = 0; i < lengthA; i++)
	{
		hash1 = (hash1 * P + B[i]) % MOD1;
		hash2 = (hash2 * P + B[i]) % MOD2;
	}

	if (hash1 == hashA1 && hash2 == hashA2)
	{
		indexListOfMatches.push_back(0);
		numberOfMatches++;
	}

	for (int i = lengthA; i < lengthB; i++)
	{
		hash1 = ((hash1 - (B[i - lengthA] * P1) % MOD1 + MOD1) * P + B[i]) % MOD1;
		hash2 = ((hash2 - (B[i - lengthA] * P2) % MOD2 + MOD2) * P + B[i]) % MOD2;

		if (hash1 == hashA1 && hash2 == hashA2)
		{
			indexListOfMatches.push_back(i - lengthA + 1);
			numberOfMatches++;
		}
	}
	
}

void Print(void)
{
	fout << numberOfMatches << '\n';
	int limitIndex;
	if (numberOfMatches > 1000)
	{
		limitIndex = 1000;
	}
	else
	{
		limitIndex = numberOfMatches;
	}
	for (int i = 0; i < limitIndex; i++)
	{
		fout << indexListOfMatches.at(i) << ' ';
	}
}

int main(void)
{
	Read();
	Match();
	Print();
	return 0;
}