Cod sursa(job #1735810)

Utilizator o_micBianca Costin o_mic Data 31 iulie 2016 05:26:24
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#define DS 26
#define LL long long
#define MOD1 666013
#define MOD2 1299709
using namespace std;

int main() {
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
	string p, s;
	vector<int> res;
	LL n, m, hp1 = 0, hp2 = 0, hs1 = 0, hs2 = 0, bs1 = 1, bs2 = 1;
	fin >> p >> s;
	m = p.size();
	n = s.size();
	if (m > n) {
		cout << 0;
		return 0;
	}
	for (int i = 0; i < m; ++i) {
		hs1 = (hs1 * DS + s[i] - 'A') % MOD1;
		hs2 = (hs2 * DS + s[i] - 'A') % MOD2;
		hp1 = (hp1 * DS + p[i] - 'A') % MOD1;
		hp2 = (hp2 * DS + p[i] - 'A') % MOD2;
		bs1 = (bs1 * DS) % MOD1;
		bs2 = (bs2 * DS) % MOD2;
	}
	for (int i = m; i < n; ++i) {
		if (hs1 == hp1 && hs2 == hp2)
			res.push_back(i - m);
		hs1 = (hs1 * DS - ((s[i-m] - 'A') * bs1) % MOD1 + (s[i] - 'A') % MOD1 + MOD1) % MOD1;
		hs2 = (hs2 * DS - ((s[i-m] - 'A') * bs2) % MOD2 + (s[i] - 'A') % MOD2 + MOD2) % MOD2;
	}
	if (hs1 == hp1 && hs2 == hp2)
		res.push_back(n - m);
	fout << res.size() << '\n';
	int res_size = min((int)res.size(), 1000);
	for (int i = 0; i < res_size; ++i)
		fout << res[i] << " ";
	return 0;
}