Cod sursa(job #1240807)

Utilizator vlad2901Vlad Berindei vlad2901 Data 12 octombrie 2014 02:01:57
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 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);
				if (total >= 1000) {
					break;
				}
			}
		}
	}
	fout << total << endl;
	for (int i = 0; i < positions.size(); ++i) {
		fout << positions[i] << " ";
	}
	return 0;
}