Cod sursa(job #388002)

Utilizator bixcabc abc bixc Data 29 ianuarie 2010 00:03:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <cstdio>
#include <string.h>

#define Nmax 2000010

char a[Nmax], b[Nmax];
int A, B;
int sol[1024], N, pi[Nmax];

void prefix () {
	
	int p = 0, i;
	for (i = 2; i <= A; i++) {
		while (p && a[p + 1] != a[i])
			p = pi[p];
		
		if (a[p + 1] == a[i])
			pi[i] = ++p;
	}
}

void kmp () {
	
	int p = 0, i;
	for (i = 1; i <= B; i++) {
		
		while (p && b[i] != a[p + 1])
			p = pi[p];
		
		if (a[p + 1] == b[i]) {
			p++;
			if (p == A) {
				N++;
				if (N <= 1000) sol[N] = i - A;
			}
		}
	}
}

int main () {

	freopen ("strmatch.in", "r", stdin);
	freopen ("strmatch.out", "w", stdout);
	
	a[0] = b[0] = ' ';
	scanf ("%s", a + 1); scanf ("%s", b + 1);
	A = strlen (a) - 1; B = strlen (b) - 1;
	
	prefix ();
	kmp ();
	
	printf ("%d\n", N);
	if (N > 1000) N = 1000;
	for (int i = 1; i <= N; i++)
		printf ("%d ", sol[i]);
	
	return 0;
}