Cod sursa(job #2449988)

Utilizator dorufDoru Floare doruf Data 21 august 2019 13:56:24
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;

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()
{
	freopen("strmatch.in", "rt", stdin);
	freopen("strmatch.out", "wt", stdout);

	scanf("%s %s", pattern, text);

	const int Mod = 101;

	rabinKarpSearch(pattern, text, Mod);

	int nrOfApparitions = indices.size();

	printf("%d\n", nrOfApparitions);

	for (int i = 0; i < min(nrOfApparitions, 1000); ++i)
		printf("%d ", indices[i]);

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