Cod sursa(job #1443843)

Utilizator mouse_wirelessMouse Wireless mouse_wireless Data 28 mai 2015 18:52:09
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <cstdio>
#include <cassert>
#include <cstring>
#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

char str[MAXLEN], pat[MAXLEN];
int slen, patlen;
int F[MAXLEN];
int matches[MAXLEN];
int mnr = 0;

void buildFail() {
	F[0] = -1;
	F[1] = 0;
	for (int i = 2; i <= patlen; i++) {
		if (pat[i - 1] == pat[F[i - 1]])
			F[i] = F[i - 1] + 1;
		else
			F[i] = 0;
	}
}

void KMP() {
	int m = 0, i = 0;
	while (m + i < slen) {
		if (i < patlen && str[m + i] == pat[i]) {
			if (i == patlen - 1)
				matches[mnr++] = m;
			i++;
		}
		else {
			if (i == 0)
				m++;
			else {
				m += i - F[i];
				i = F[i];
			}
		}
	}
}

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