Cod sursa(job #2449979)

Utilizator dorufDoru Floare doruf Data 21 august 2019 13:39:41
Problema Potrivirea sirurilor Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

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

const int alphabethSize = 256;
const int maxTextSize = 2000005;

vector <int> indices;

void rabinKarpSearch(char pattern[], char text[], const int Mod);

char text[maxTextSize];
char pattern[maxTextSize];

int main()
{
	fin >> pattern >> text;
	const int Mod = 666013;

	rabinKarpSearch(pattern, text, Mod);

	fout << indices.size() << '\n';
	for (int i = 0; i < indices.size(); ++i)
		fout << indices[i] << ' ';

	fin.close();
	fout.close();
	return 0;
}

void rabinKarpSearch(char pattern[], char text[], int Mod)
{
	int patternSize = strlen(pattern);
	int textSize = strlen(text);

	int hvPattern = 0;
	int hvText = 0;
	int h = 1;

	for (int i = 0; i < patternSize - 1; ++i)
		h = (h * alphabethSize) % Mod;

	for (int i = 0; i < patternSize; ++i)
	{
		hvPattern = (alphabethSize * hvPattern + pattern[i]) % Mod;
		hvText = (alphabethSize * hvText + text[i]) % Mod;
	}

	for (int i = 0; i <= textSize - patternSize; ++i)
	{
		if (hvPattern == hvText)
		{
			int j;
			for (j = 0; j < patternSize; ++j)
			{
				if (text[i + j] != pattern[j])
					break;
			}

			if (j == patternSize)
				indices.push_back(i);
		}

		if (i < textSize - patternSize)
		{
			hvText = (alphabethSize * (hvText - text[i] * h) + text[i + patternSize]) % Mod;
			if (hvText < 0)
				hvText += Mod;
		}
	}
}