Cod sursa(job #1504628)

Utilizator meriniucrMeriniuc Razvan- Dumitru meriniucr Data 17 octombrie 2015 23:25:44
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <string.h>
#include <iostream>

using namespace std;

int hashString(string str, int length)
{
	int val;

	val = 0;
	for (int i = 0; i < length; i += 1)
	{
		val = val * 31 + str[i];
		if (val > 666012)
			val %= 666013;
	}
	return val;
}

int fix(char c, int power)
{
	int result;

	if (power == 2)
		return c * c;
	if (power == 1)
		return c;
	if (power % 2 == 1)
		return c * (fix(c, power - 1) % 666013);
	else
	{
		result = fix(c, power / 2) % 666013;
		return ((result * result) % 666013);
	}
}

int main()
{
	ifstream mama("strmatch.in");
	ofstream tata("strmatch.out");

	string text;
	string pattern;
	int patternLength;
	int textLength;
	int patternHash;
	int textHash;
	int counter;
	int position[100000];

	getline(mama, pattern);
	getline(mama, text);
	patternLength = pattern.size();
	textLength = text.size();
	patternHash = hashString(pattern, patternLength);
	textHash = hashString(text.substr(0, patternLength), patternLength);
	if (patternHash == textHash and text.substr(0, patternLength) == pattern)
		position[counter++] = 0;
	textLength -= patternLength;
	for (int i = 1; i < textLength; i += 1)
	{
		textHash = ((textHash - (text[i - 1] * fix(31, patternLength - 1)) % 666013) * 31 % 666013 + text[i + patternLength - 1]) % 666013;
		if (patternHash == textHash and text.substr(i, patternLength) == pattern)
			position[counter++] = i;
	}
	tata << counter << '\n';
	for (int i = 0; i < counter; i += 1)
		tata << position[i] << " ";
	return 0;
}