Cod sursa(job #1614593)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 26 februarie 2016 00:05:23
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <string.h>
#define modf 100007
#define mods 100021
#define NMax 2000001
#define bs 73
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int hashf, hashs, p1, p2, foundf, founds, n, poz[NMax], i, saa, baa;
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*bs + a[i]) % modf;
		hashs = (hashs*bs + a[i]) % mods;
		if (i != 0) {
			p1 = (p1*bs) % modf;
			p2 = (p2*bs) % mods;
		}
	}
	if (saa > baa) {
		g << "0\n";
		return 0;
	}
	for (i = 0; i<saa; i++) {
		foundf = (foundf*bs + b[i]) % modf;
		founds = (founds*bs + b[i]) % mods;
	}
	if (foundf == hashf && founds == hashs)
		poz[++n] = 0;
	for (i = saa; i<baa; i++) {
		foundf = ((foundf - (p1*b[i - saa]) % modf + modf)*bs + b[i]) % modf;
		founds = ((founds - (p2*b[i - saa]) % mods + mods)*bs + b[i]) % mods;
		if (foundf == hashf && founds == hashs)
			poz[++n] = i - saa + 1;
	}
	g << n << "\n";
	for (i = 1; i <= n && i <= 1000; i++)
		g << poz[i] << " ";
	g << "\n";
	return 0;
}