Cod sursa(job #596660)

Utilizator mihai.ortelecanOrtelecan Mihai alexandru mihai.ortelecan Data 18 iunie 2011 11:55:38
Problema Potrivirea sirurilor Scor 22
Compilator c Status done
Runda Arhiva educationala Marime 1.28 kb
/*
 * strmatch.c
 *
 *  Created on: Jun 17, 2011
 *      Author: mihai
 */

#include <stdio.h>
#define MAX 2000002
#define min(a, b) ((a < b) ? a : b)

char A[MAX], B[MAX], pi[MAX];
int Asize, Bsize, poz[1002];

void make_prefix() {

	int k = 0, q;
	pi[1] = 0;

	for (q = 2; q <= Asize; q++) {

		while (k > 0 && A[k + 1] != A[q])
			k = pi[k];
		if (A[k + 1] == A[q])
			++k;
		pi[q] = k;
	}
}

int main() {

	int q = 0, i, aparitii = 0;

	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);

	scanf("%s", A);
	scanf("%s", B);

	while ((A[Asize] >= 'A' && A[Asize] <= 'Z') || (A[Asize] >= 'a' && A[Asize] <= 'z') || (A[Asize] >= '0' && A[Asize] <= '9'))
		++Asize;
	while ((B[Bsize] >= 'A' && B[Bsize] <= 'Z') || (B[Bsize] >= 'a' && B[Bsize] <= 'z') || (B[Bsize] >= '0' && B[Bsize] <= '9'))
		++Bsize;

	for (i = Asize; i; i--)
		A[i] = A[i - 1];
	A[0] = ' ';
	for (i = Bsize; i; i--)
		B[i] = B[i - 1];
	B[0] = ' ';

	make_prefix();

	for (i = 1; i <= Bsize; i++) {

		while (q && A[q + 1] != B[i])
			q = pi[q];
		if (A[q + 1] == B[i])
			++q;
		if (q == Asize) {
			q = pi[q];
			++aparitii;
			if (aparitii <= 1000)
				poz[aparitii] = i - Asize;
		}
	}

	printf("%d\n", aparitii);

	for (i = 1; i <= min(1000, aparitii); i++) {
		printf("%d ", poz[i]);
	}
	printf("\n");

	return 0;
}