Cod sursa(job #964604)

Utilizator gabrieligabrieli gabrieli Data 21 iunie 2013 18:10:23
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
//BEGIN CUT
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

//END CUT
struct Rabin_Karp {
	const int base = 73, modulo1 = 100007, modulo2 = 100021;

	vector<int> get_matches(const string &text, const string &pattern) {
		vector<int> matches;

		int hp1, hp2, hs1, hs2;
		int base_pow1 = 1, base_pow2 = 1;
		hp1 = hp2 = pattern[0];
		hs1 = hs2 = text[0];
		for (int i = 1; i < pattern.size(); ++i)
		{
			base_pow1 = (base_pow1 * base) % modulo1;
			base_pow2 = (base_pow2 * base) % modulo2;

			hp1 = (hp1 * base + pattern[i]) % modulo1;
			hs1 = (hs1 * base + text[i]) % modulo1;
			hp2 = (hp2 * base + pattern[i]) % modulo2;
			hs2 = (hs2 * base + text[i]) % modulo2;
		}			

		if (hp1 == hs1 && hp2 == hs2)
			matches.push_back(0);

		for (int i = pattern.size(); i < text.size(); ++i)
		{
        	hs1 = (base * ((hs1 - base_pow1 * text[i-pattern.size()]) % modulo1 + modulo1)
        			+ text[i]) % modulo1;
        	hs2 = (base * ((hs2 - base_pow2 * text[i-pattern.size()]) % modulo2 + modulo2)
        			+ text[i]) % modulo2;

			if (hp1 == hs1 && hp2 == hs2)
				matches.push_back(i - pattern.size() + 1);
		}

		return matches;
	}
};
//BEGIN CUT
int main()
{
 	ifstream fin("strmatch.in");
	ofstream fout ("strmatch.out");

	Rabin_Karp rp;
	string text, pattern;

	fin >> pattern >> text;
	vector<int> matches = rp.get_matches(text, pattern);

	fout << matches.size() << '\n';
	/*
	for (auto &pos : matches)
		fout << pos << ' ';
		*/
	for (int i = 0; i < 1000 && i < mathces.size(); ++i)
		fout << matches[i] << ' ';
	fout << '\n';

	fout.close();
 
	return 0;
}
//END CUT