Cod sursa(job #1908992)

Utilizator lflorin29Florin Laiu lflorin29 Data 7 martie 2017 11:18:02
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <bits/stdc++.h>

using namespace std;

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

const int P = 1e9 + 7;

const int nMax = 2e6;

int64_t power[nMax + 2];

void Precalcpower() {
	power[0] = 1;

	for (int i = 1; i <= nMax; ++i)
		power[i] = power[i - 1] * P;
}

struct Sir {
	string s;
	vector<int64_t>poly;
	Sir(const string &s) : s(s) {
		poly.resize(s.size());
		poly[0] = s[0];

		for (int i = 1; i < s.size(); ++i) {
			poly[i] = poly[i - 1] * P + s[i];
		}
	}
	int64_t BigHash() {
		return poly.back();
	}
	int64_t get(int i, int j) {
		if (i == 0)
			return poly[j];

		return poly[j] - poly[i - 1] * power[j - i + 1];
	}
};

int main() {
	string a, b;
	fin >> a >> b;
	Precalcpower();
	Sir S1(a), S2(b);
	int64_t need = S1.BigHash();
	vector<int>match;

	for (int i = a.size() - 1; i < b.size(); ++i) {
		if (S2.get(i - a.size() + 1, i) == need)
			match.push_back(i - a.size() + 1);
	}

	fout << match.size() << '\n';

	for (int i = 0; i < min(1000, (int)match.size()); ++i)
		fout << match[i] << ' ';
	return 0;
}