Cod sursa(job #1446414)

Utilizator mouse_wirelessMouse Wireless mouse_wireless Data 1 iunie 2015 19:55:29
Problema Potrivirea sirurilor Scor 28
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <cstdio>
#include <cassert>
#include <cstring>
#include <algorithm>
#define _submit
#ifdef _submit
#define InFile "strmatch.in"
#define OutFile "strmatch.out"
#else
#define InFile "fis.in"
#define OutFile "fis.out"
#endif

#define MAXLEN 2010000
#define MAXDLEN 4010000

char strpat[MAXDLEN], *str, *pat;
int strpatlen, slen, patlen;
int F[MAXDLEN];
char matched[MAXLEN];
int mnr = 0;

void buildFail() {
	F[0] = -1;
	for (int i = 1; i <= strpatlen; i++) {
		int k = F[i - 1];
		while ((k != -1) && (strpat[i - 1] != strpat[k]))
			k = F[k];
		F[i] = k + 1;
	}
}

void buildZ() {
	for (int i = patlen; i < slen + patlen; i++)
	if (i - F[i] >= patlen && F[i] >= patlen) {
		mnr++;
		matched[i - F[i] - patlen] = 1;
	}
}

int main() {
	assert(freopen(InFile, "r", stdin));
	assert(freopen(OutFile, "w", stdout));
	pat = strpat;
	scanf("%s", pat);
	patlen = strlen(pat);
	str = strpat + patlen;
	scanf("%s", str);
	slen = strlen(str);
	strpatlen = patlen + slen;
	buildFail();
	buildZ();
	int printed = 0;
	printf("%d\n", mnr);
	for (int i = 0; i < slen && printed < 1000; i++)
	if (matched[i]) {
		printed++;
		printf("%d ", i);
	}
	printf("\n");
	return 0;
}