Cod sursa(job #3264976)

Utilizator EricDimiericdc EricDimi Data 26 decembrie 2024 10:51:47
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

const int MOD = 1'000'000'007;
const int MAX_N = 2'000'000;
const int MAX_AP = 1'000;
const int BASE = 127;

long long textHash[MAX_N + 1], pwr[MAX_N + 1];
long long patternHash, leftHash, rightHash, currHash;
int patternLen, textLen, nr;
int pos[MAX_AP + 1];

int main()
{
	string pattern, text;
	f >> pattern >> text;

	patternLen = pattern.size();
	textLen = text.size();

	pwr[0] = 1;
	for (int i = 1; i <= MAX_N; i++)
		pwr[i] = (pwr[i - 1] * BASE) % MOD;

	patternHash = 0;
	for (int i = 0; i < patternLen; i++)
	{
		patternHash *= BASE;
		patternHash += (pattern[i] - '0');
		patternHash %= MOD;
	}

	for (int i = 0; i < textLen; i++)
	{
		textHash[i + 1] = textHash[i];
		textHash[i + 1] *= BASE;
		textHash[i + 1] += (text[i] - '0');
		textHash[i + 1] %= MOD;
	}

	for (int i = patternLen; i <= textLen; i++)
	{
		rightHash = textHash[i];
		leftHash = (pwr[patternLen] * textHash[i - patternLen]) % MOD;
		currHash = (rightHash - leftHash + MOD) % MOD;

		if (currHash == patternHash)
		{
			++nr;
			if (nr <= MAX_AP)
				pos[nr] = i - patternLen;
		}
	}

	g << nr << '\n';
	for (int i = 1; i <= nr; i++)
		g << pos[i] << ' ';

	f.close();
	g.close();
    return 0;
}