Cod sursa(job #143704)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 26 februarie 2008 19:58:34
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <cstdio>
#include <cstring>

const int NMAX = 1 << 21;

char A[NMAX], B[NMAX];
int pi[NMAX], R[NMAX];

int main(void) {
	freopen("strmatch.in", "rt", stdin);
	freopen("strmatch.out", "wt", stdout);
	int N, M, NR = 0;
	int i, j;

	scanf(" %s %s", A, B);
	N = strlen(A); M = strlen(B);

	pi[0] = pi[1] = 0;
	for (i = 1, j = 0; i < N; ++i) {
		while (j > 0 && A[i] != A[j]) j = pi[j];
		if (A[i] == A[j]) ++j;
		pi[i+1] = j;
	}

	for (i = j = 0; i < M; ++i) {
		while (j > 0 && A[j] != B[i]) j = pi[j];
		if (A[j] == B[i]) ++j;
		if (j == N) {
			R[NR++] = i - N + 1;
			j = pi[j];
		}
	}

	printf("%d\n", NR);
	if (NR > 1000) NR = 1000;
	for (i = 0; i < NR; ++i)
		printf("%d ", R[i]);
	printf("\n");

	return 0;
}