Cod sursa(job #1446474)

Utilizator mouse_wirelessMouse Wireless mouse_wireless Data 1 iunie 2015 21:57:28
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <cstring>
using namespace std;
#define _submit
#ifdef _submit
#define InFile "strmatch.in"
#define OutFile "strmatch.out"
#else
#define InFile "fis.in"
#define OutFile "fis.out"
#endif

#define NRDMAX 400010
#define NRMAX 200010

char patstr[NRDMAX], *pat, *str;
int Z[NRDMAX];
int patlen, slen, patstrlen;
int matches[1000];
int mnr;

void buildZ() {
	int L = 0, R = 0;
	for (int k = 1; k < patstrlen; k++) {
		Z[k] = 0;
		if (k > R) {
			for (R = k; R < patstrlen; R++, Z[k]++)
			if (patstr[R] != patstr[R - k])
				break;
			L = k; R--;
		}
		else {
			int kprim = k - L; //+ 1;
			int B = R - k + 1;
			int C = Z[kprim];
			if (C < B)
				Z[k] = C;
			else {
				int A = R - L + 1;
				int cpA = A;
				for (++R; R < patstrlen; ++R, ++A)
				if (patstr[R] != patstr[A])
					break;
				L = k;
				R--;
				Z[k] = R - k + cpA;
			}
		}
	}
}

int main() {
	assert(freopen(InFile, "r", stdin));
	assert(freopen(OutFile, "w", stdout));
	pat = patstr;
	scanf("%s", pat);
	patlen = strlen(pat);
	str = patstr + patlen;
	scanf("%s", str);
	slen = strlen(str);
	patstrlen = patlen + slen;
	buildZ();
	mnr = 0;
	for (int i = patlen; i < patstrlen; i++)
	if (Z[i] >= patlen) {
		if (mnr < 1000)
			matches[mnr] = i - patlen;
		mnr++;
	}
	printf("%d\n", mnr);
	int toPrint = (mnr < 1000) ? mnr : 1000;
	for (int i = 0; i < toPrint; i++)
		printf("%d ", matches[i]);
	return 0;
}