Cod sursa(job #1909014)

Utilizator lflorin29Florin Laiu lflorin29 Data 7 martie 2017 11:22:56
Problema Potrivirea sirurilor Scor 78
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 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 Plen;

int64_t Code(const string &s) {
	int64_t res = s[0];

	for (int i = 1; i < s.size(); ++i)
		res = res * P + s[i];

	return res;
}

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) {
		return poly[j] - poly[i - 1] * Plen;
	}
};

int main() {
	string a, b;
	fin >> a >> b;
	Plen = 1;

	for (int i = 1; i <= a.size(); ++i)
		Plen *= P;

	Sir S2(b);
	int64_t need = Code(a);
	vector<int>match;
	int nrMatches = 0;

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

			if (nrMatches <= 1000)
				match.push_back(i - a.size() + 1);
		}
	}

	fout << nrMatches << '\n';

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

	return 0;
}