Cod sursa(job #982888)

Utilizator cosmo0093Raduta Cosmin cosmo0093 Data 10 august 2013 14:11:30
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include <fstream>
#include <string>
#include <vector>

const unsigned pb = 257;
const unsigned MOD = 1000000007;

long long pow(long long x, unsigned a)
{
	if(a == 0) return 1;
	if(a == 1) return x % MOD;
	if(a % 2 == 0) return (pow((x * x) % MOD, a / 2)) % MOD;
	return (x * pow((x * x) % MOD, a / 2)) % MOD;
}

long long getHash(std::string& str, unsigned a, unsigned b)
{
	long long ret = 0;
	for(unsigned i = a; i < b; i++)
		ret = ret * pb + str[i], ret %= MOD;
	return ret;
}

bool comps(std::string& str, std::string& lstr, unsigned start)
{
	for(unsigned i = 0; i < str.length(); i++)
		if(str[i] != lstr[start + i]) return false;
	return true;
}

unsigned rabin(std::string& str, std::string& lstr, unsigned *myV)
{
	unsigned nr = 0;
	long long comp = getHash(str, 0, str.length());
	long long ret = getHash(lstr, 0, str.length());
	long long power = pow(pb, str.length());
	if(ret == comp)
	{
		if(comps(str, lstr, 0)) 
		{
			myV[0] = 0;
			nr++;
		}
	}
	for(unsigned i = str.length(); i < lstr.length(); i++)
	{
		ret = ret * pb + lstr[i];
		ret %= MOD;
		ret -= (power * lstr[i - str.length()]) % MOD;
		if(ret < 0) ret += MOD;
		if(ret == comp)
		{
			if(comps(str, lstr, i - str.length() + 1))
			{
				if(nr < 1000) myV[nr] = i - str.length() + 1;
				nr++;
			}
		}
	}
	return nr;
}

int main()
{
	std::ifstream in("strmatch.in");
	std::ofstream out("strmatch.out");
	std::string str, lstr;
	getline(in, str);
	getline(in, lstr);
	unsigned *myV = new unsigned[1000];
	unsigned nr = rabin(str, lstr, myV);
	out << nr << '\n';
	int a;
	if(nr < 1000) a = nr;
	else a = 1000; 
	for(int i = 0; i < a; i++)
		out << myV[i] << ' ';
	return 0;
}