Cod sursa(job #431812)

Utilizator bixcabc abc bixc Data 1 aprilie 2010 14:06:56
Problema Potrivirea sirurilor Scor 36
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 n, m, nr;
int sol[1010], pi[Nmax];

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 = 1;
	for (int i = 1; i <= m; i++) {
		while (p && B[i] != A[p + 1]) 
			p = pi[p];
		
		if ( B[i] == A[p + 1] ) {
			p++;
			if (p == n) {
				nr++;
				if (nr <= 100) 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);
	for (int i = 1; i <= nr; i++)
		printf ("%d ", sol[i]);
	
	return 0;
}