Cod sursa(job #964617)

Utilizator gabrieligabrieli gabrieli Data 21 iunie 2013 18:31:02
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.56 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");

	string text, pattern;
	fin >> pattern >> text;
	/*
	Rabin_Karp rp;

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

	fout << matches.size() << '\n';
	for (auto &pos : matches)
		fout << pos << ' ';
	fout << '\n';
    */

	const int base = 269, modulo1 = 611833, modulo2 = 611837;
	int matches[1012], m=0;
 	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[m++]=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)
		{
			if (m < 1000)
				matches[m] = i - pattern.size() + 1;
			m++;
		}
	} 

	fout << m << '\n';
	for (int i = 0; i < m && i < 1000; ++i)
		fout << matches[i] << ' ';
	fout << endl;
	
	fout.close();
 
	return 0;
}
//END CUT