Cod sursa(job #1274281)

Utilizator mircea.dobreanuMircea Dobreanu mircea.dobreanu Data 23 noiembrie 2014 17:57:41
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <cstdlib>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int logpow(int base, int e)
{
	const int MOD = 1e9 + 7;
	if (base == 1 || base == 0)
		return base;
	base %= MOD;

	if (e == 1)
		return base;

	int square = (base * base) % MOD;
	if (e % 2 == 0)
		return logpow(square, e / 2) % MOD;
	else
		return (base * (logpow(square, e / 2) % MOD)) % MOD;
}

int hashFun(int currHash, int length, char prevChar, char nextChar)
{
	const int kPrimeBase = 257;
	const int MOD = 1e9 + 7;

	currHash = ((currHash * kPrimeBase) % MOD);
	currHash = abs(currHash - (prevChar * logpow(kPrimeBase, length) % MOD)) % MOD;
	currHash = (currHash + nextChar) % MOD;

	return currHash;
}


void matchStrings(string& s, string& p, vector<int>& matches)
{
	size_t n = s.size(), m = p.size();
	int hs = 0, hp = 0;
	for (size_t i = 0; i < m; ++i)
	{
		hs = hashFun(hs, i, '\0', s[i]);
		hp = hashFun(hp, i, '\0', p[i]);
	}
	for (size_t i = 0; i < n - m + 1; ++i)
	{
		//Compute new hash
		if (i > 0)
			hs = hashFun(hs, m, s[i - 1], s[i + m - 1]);
		//Hashes match
		if (hs == hp && matches.size() < 1000)
			matches.push_back(i);
	}
}

int main()
{
	string s, p;
	fin >> p >> s;

	vector<int> matches;
	matchStrings(s, p, matches);

	fout << matches.size() << '\n';
	for (size_t i = 0; i < matches.size(); ++i)
		fout << matches[i] << ' ';
	fout << '\n';
	return 0;
}