Cod sursa(job #1735815)

Utilizator o_micBianca Costin o_mic Data 31 iulie 2016 05:48:57
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#define DS 62
#define DN 2000005
#define MOD1 666013
#define MOD2 1299709
using namespace std;

int comp_code(char c) {
	if (c <= '9')
		return c - '0';
    if (c <= 'Z')
        return c - 'A' + 10;
    return c - 'a' + 36;
}

int res[DN];

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