Cod sursa(job #1240810)

Utilizator vlad2901Vlad Berindei vlad2901 Data 12 octombrie 2014 02:24:37
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.92 kb
#include <string>
#include <fstream>
#include <vector> 
#include <iostream> 

using namespace std;

#define MOD1 100007
#define MOD2 666013
#define BASE 79

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

int main() {
	string s, p;
	fin >> p >> s;
	if (p.size() > s.size()) {
		fout << 0;
		return 0;
	}
	int lp = p.size();
	int ls = s.size();
	int phash1 = 0, phash2 = 0, shash1 = 0, shash2 = 0, val1 = 1, val2 = 1;
	for (int i = 0; i < lp - 1; ++i) {
		phash1 = (phash1 * BASE + p[i]) % MOD1;
		shash1 = (shash1 * BASE + s[i]) % MOD1;
		phash2 = (phash2 * BASE + p[i]) % MOD2;
		shash2 = (shash2 * BASE + s[i]) % MOD2;
		// cout << phash1 << " " << shash1 << endl; 				
		val1 = (val1 * BASE) % MOD1;
		val2 = (val2 * BASE) % MOD2;
	}
	phash1 = (phash1 * BASE + p[lp - 1]) % MOD1;
	shash1 = (shash1 * BASE + s[lp - 1]) % MOD1;
	phash2 = (phash2 * BASE + p[lp - 1]) % MOD2;
	shash2 = (shash2 * BASE + s[lp - 1]) % MOD2;
	// cout << phash1 << " " << shash1 << endl; 
	int total = 0;
	vector<int> positions;
	if (phash2 == shash2 && phash1 == shash1) {
		// int ok = 1;
		// for (int j = 0; j < lp; ++j) {
		// 	if (p[j] != s[j]) {
		// 		ok = 0;
		// 		break;
		// 	}
		// }
		// if (ok) {
			++total;
			positions.push_back(0);
		// }
	}
	for (int i = 1; i < ls - lp + 1; ++i) {
		shash1 = ((shash1 - (val1 * s[i-1]) % MOD1 + MOD1) * BASE + s[i + lp - 1]) % MOD1;
		shash2 = ((shash2 - (val2 * s[i-1]) % MOD2 + MOD2) * BASE + s[i + lp - 1]) % MOD2;
		// cout << phash1 << " " << shash1 << endl; 
		if (phash2 == shash2 && phash1 == shash1) {
			// int ok = 1;
			// for (int j = i; j < i + lp; ++j) {
			// 	if (p[j - i] != s[j]) {
			// 		ok = 0;
			// 		break;
			// 	}
			// }
			// if (ok) {
				++total;
				positions.push_back(i);
			// }
		}
	}
	fout << total << endl;
	for (int i = 0; i < positions.size() && i < 1000; ++i) {
		fout << positions[i] << " ";
	}
	return 0;
}