Cod sursa(job #2211262)

Utilizator AlexDabuDabu Alexandru AlexDabu Data 9 iunie 2018 17:26:37
Problema Potrivirea sirurilor Scor 26
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string>

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 hash , hashpattern = Hash((int)A.at(0) , (int)A.at(A.size() - 1));
	bool match = true;
	string sub = B.substr(0, A.size());

	hash = Hash((int)sub.at(0) , (int)sub.at(sub.size() - 1));
	if (hash == hashpattern)
	{
		if (A == sub)
		{
			numberOfMatches++;
			indexListOfMatches.push_back(0);
		}
	}
	for (unsigned int i = 1; i < B.size() - A.size() + 1; i++)
	{
		sub = B.substr(i, A.size());
		hash = Hash((int)sub.at(0), (int)sub.at(sub.size() - 1));
		if (hash == hashpattern)
		{
			if (A == sub)
			{
				numberOfMatches++;
				indexListOfMatches.push_back(i);
			}
		}
	}
}

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