Cod sursa(job #1182695)

Utilizator vlasinalinVlasin Alin vlasinalin Data 7 mai 2014 09:53:08
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include <stdio.h>
#include <limits.h>
#include <iostream>
#include <fstream>
#include <string>
#include <forward_list>
#include <queue>
using namespace std;

#define MAXN 2000001

#define IN "strmatch.in"
#define OUT "strmatch.out"

#define LARGE_INT_PRIME 1999999973

int m, n;
string word, text;
int wordHash;
int matchesFound, matchesTextIndex[MAXN], wordLength, textLength;

void read_input()
{
	ifstream fin(IN);

	getline(fin, word);
	getline(fin, text);

	fin.close();

	wordLength = word.length();
	textLength = text.length();
}

void computeWordHash()
{
	for (int i = 0; i < wordLength; ++i)
	{
		wordHash += word[i];
	}
}

void checkForEquality(int ti)
{
	bool areMatch = true;
	for (int i = 0; i < wordLength; ++i)
	{
		if (word[i] != text[i + ti])
		{
			areMatch = false;
			break;
		}
	}
	if (areMatch)
	{
		matchesTextIndex[matchesFound++] = ti;
	}
}

void resolve()
{
	computeWordHash();

	int curHash = 0;
	for (int i = 0; i < wordLength; ++i)
	{
		curHash += text[i];
	}

	if (curHash == wordHash)
	{
		checkForEquality(0);
	}

	for (int i = wordLength; i < textLength; ++i)
	{
		curHash = curHash + text[i] - text[i - wordLength];
		if (curHash == wordHash)
		{
			checkForEquality(i - wordLength + 1);
		}
	}
}

void print_solution()
{
	ofstream fout(OUT);
	fout << matchesFound << '\n';
	for (int i = 0; i < matchesFound; ++i)
	{
		fout << matchesTextIndex[i] << ' ';
	}
	fout.close();
}

int main()
{
	read_input();

	resolve();

	print_solution();

	//char x;
	//cin >> x;

	return 0;
}