Cod sursa(job #756105)

Utilizator voyagerSachelarie Bogdan voyager Data 9 iunie 2012 02:01:15
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <cstdio>
#include <cstdlib>
#include <cstring>

#define FOR(AA,BB,CC) for(int AA=(BB); AA<(CC); ++AA)
#define NMAX 2000010

char A[NMAX], N, B[NMAX], M;
int P[NMAX];
int num_matches, matches[1000];

void build_prefix() {
	int k = -1;
	P[0] = -1;
	N = strlen(A);
	FOR(q, 1, N) {
		while (k>=0 && A[k+1] != A[q])
			k = P[k];
		if (A[k+1] == A[q])
			++k;
		P[q] = k;
	}
}

int main() {
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	gets(A);
	gets(B);

	build_prefix();

	M = strlen(B);
	int k = -1;
	FOR(i, 0, M) {
		while (k>=0 && A[k+1] != B[i])
			k = P[k];
		if (A[k+1] == B[i])
			++k;
		if (k == N-1) {
			if (num_matches < 1000)
				matches[num_matches++] = i - N + 1;
			k = P[k];
		}
	}

	printf("%d\n", num_matches);
	FOR(i, 0, num_matches > 1000 ? 1000 : num_matches) {
		printf("%d ", matches[i]);
	}
	puts("");

	fclose(stdout);
}