Cod sursa(job #1240809)

Utilizator vlad2901Vlad Berindei vlad2901 Data 12 octombrie 2014 02:10:52
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <string>
#include <fstream>
#include <vector> 
#include <iostream> 

using namespace std;

#define MOD 100007
#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 phash = 0, shash = 0, val = 1;
	for (int i = 0; i < lp - 1; ++i) {
		phash = (phash * BASE + p[i]) % MOD;
		shash = (shash * BASE + s[i]) % MOD;
		// cout << phash << " " << shash << endl; 				
		val = (val * BASE) % MOD;
	}
	phash = (phash * BASE + p[lp - 1]) % MOD;
	shash = (shash * BASE + s[lp - 1]) % MOD;
	// cout << phash << " " << shash << endl; 
	int total = 0;
	vector<int> positions;
	if (phash == shash) {
		// 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) {
		shash = ((shash - (val * s[i-1]) % MOD + MOD) * BASE + s[i + lp - 1]) % MOD;
		// cout << phash << " " << shash << endl; 
		if (phash == shash) {
			// 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;
}