Cod sursa(job #1614591)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 26 februarie 2016 00:04:57
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <string.h>

#define NMax 2000001
#define BASE 73
using namespace std;

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

int n, poz[NMax], i, saa, baa;
unsigned long long hashf, p1, p2, foundf;
char a[NMax], b[NMax];
int main()
{
	f.get(a, 2000001);
	f.get();
	f.get(b, 2000001);

	p1 = 1;
	p2 = 1;

	saa = strlen(a);
	baa = strlen(b);

	for (i = 0; i < saa; i++) {
		hashf = hashf*BASE + a[i];

		if (i != 0) {
			p1 = p1*BASE;
			p2 = p2*BASE;
		}
	}

	for (i = 0; i < saa; i++)
		foundf = foundf*BASE + b[i];

	if (foundf == hashf)
		poz[++n] = 0;

	for (i = saa; i < baa; i++) {
		foundf = foundf - (p1*b[i - saa])*BASE + b[i];
		if (foundf == hashf)
			poz[++n] = i - saa + 1;
	}

	g << n << "\n";

	for (i = 1; i <= n && i <= 1000; i++)
		g << poz[i] << " ";

	g << "\n";
	return 0;
}