Cod sursa(job #580136)

Utilizator bixcabc abc bixc Data 12 aprilie 2011 19:33:10
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <cstdio>
#include <algorithm>
#include <string.h>
using namespace std;

#define Nmax 2000010

int n, m, nr;
char A[Nmax], B[Nmax];
int pi[Nmax], sol[1010];

void prefix () {

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

		pi[i] = p;
	}
}

void kmp () {
	
	int i, p = 0;
	for (i = 1; i <= m; i++) {
		while (p && A[p + 1] != B[i]) p = pi[p];
		if (A[p + 1] == B[i]) p++;

		if (p == n) {
			nr++;
			if (nr <= 1000) sol[nr] = i - n;
		}
	}
}

int main () {

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

	A[0] = ' ';
	scanf ("%s", A + 1); n = strlen (A) - 1;
	B[0] = ' ';
	scanf ("%s", B + 1); m = strlen (B) - 1;

	prefix ();
	kmp ();

	printf ("%d\n", nr);
	int i, N = min (1000, nr);
	for (i = 1; i <= N; i++)
		printf ("%d ", sol[i]);

	return 0;
}