Cod sursa(job #1614571)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 25 februarie 2016 23:50:03
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <string.h>

#define NMax 2000010
#define BASE 73

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

int len1, len2, matches[NMax], nm;
unsigned long long H[NMax], powB[NMax];
char str1[NMax], str2[NMax];

unsigned long long getHash(int start, int finish)
{
	return (H[finish] - H[start - 1] * powB[finish - start + 1]);
}

int main()
{
	f.getline(str1 + 1, 2000001);
	f.getline(str2 + 1, 2000001);
	
	len1 = strlen(str1 + 1);
	len2 = strlen(str2 + 1);

	powB[0] = 1;
	for (int i = 1; i <= len2; i++)
		powB[i] = powB[i - 1] * BASE;

	unsigned long long hashMatch = 0;
	for (int i = 1; i <= len1; i++)
		hashMatch = hashMatch * BASE + str1[i];

	for (int i = 1; i <= len2; i++)
		H[i] = H[i - 1] * BASE + str2[i];

	for (int i = len1; i <= len2; i++) {
		if (getHash(i - len1 + 1, i) == hashMatch) {
			if (nm < 1000)
				matches[++nm] = i - len1 + 1;
			else
				++nm;
		}
	}

	g << nm << "\n";
	for (int i = 1; i <= nm && i <= 1000; i++)
		g << matches[i] - 1 << " ";

	return 0;
}