Cod sursa(job #552443)

Utilizator bixcabc abc bixc Data 12 martie 2011 12:57:16
Problema Potrivirea sirurilor Scor 36
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;

#define Nmax 2000010

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

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

void kmp () {

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

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

int main () {

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

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

	prefix ();
	kmp ();

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

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

	return 0;
}