Cod sursa(job #482824)

Utilizator andreitheo87Teodorescu Andrei-Marius andreitheo87 Data 5 septembrie 2010 16:32:13
Problema Potrivirea sirurilor Scor 26
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main() {
	ifstream fin("strmatch.in");
	ofstream fout("strmatch.out");
	string a, b;
	fin >> a;
	fin >> b;
	if (a.size() > b.size()) {
		fout << 0 << endl;
	}
	long long hasha = 0, hashb = 0;
	long long hashaa = 0, hashbb = 0;
	long long pow_size_a = 1;
	long long pow_size_aa = 1;
	for (int i = 0; i < a.size(); i++) {
		hasha = (131321 * hasha  + a[i]) % 100000001;
		hashaa = (13131 * hashaa  + a[i]) % 10000001;
		hashb = (131321 * hashb  + b[i]) % 100000001;
		hashbb = (13131 * hashbb  + b[i]) % 10000001;
		pow_size_a = (pow_size_a * 131321) % 100000001;
		pow_size_aa= (pow_size_aa * 13131) % 10000001;
	}
	vector<int> pos;
	for (int i = a.size() - 1; i < b.size(); i++) {
		if (hasha == hashb && hashaa == hashbb) {
			pos.push_back(i - a.size() + 1);
		}
		if (i != b.size() - 1) {
			hashb = (131321 * hashb  + b[i + 1]) % 100000001;
			hashbb = (13131 * hashbb  + b[i + 1]) % 10000001;
			hashbb = (hashbb + 256ll * 10000001ll - b[i - a.size() + 1] * pow_size_aa) % 10000001;
			hashb = (hashb + 256ll * 100000001ll - b[i - a.size() + 1] * pow_size_a) % 100000001;
		}
	}
	fout << pos.size() << endl;
	for(int i = 0; i < pos.size(); i++) {
		fout << pos[i] << " ";
	}
	fout << endl;
	return 0;
}