Cod sursa(job #574425)

Utilizator Addy.Adrian Draghici Addy. Data 7 aprilie 2011 10:34:19
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <cstdio>
#include <cstring>

#define NMAX 2000050

char A[NMAX], B[NMAX];
int V[1024], pi[NMAX], NA, NB, sol, k, i;

int main () {
	
	freopen ("strmatch.in", "r", stdin);
	freopen ("strmatch.out", "w", stdout);
	
	scanf ("%s\n%s", A + 1, B + 1); 
	A[0] = ' '; B[0] = ' '; NA = strlen (A)- 1, NB = strlen (B) - 1;
	
	pi[1] = 0;
	for (i = 2; i <= NA; i++) {
		
		while (k > 0 && A[i] != A[k + 1])
			k = pi[k];
		
		if (A[i] == A[k + 1])
			k++;
		
		pi[i] = k;
	}
	
	k = 0;
	for (i = 1; i <= NB; i++) {
		
		while (k > 0 && B[i] != A[k + 1])
			k = pi[k];
		
		if (B[i] == A[k + 1])
			k++;
		
		if (k == NA) {
			sol++;
			
			if (sol <= 1000) V[sol] = i - NA;
		}
	}
	
	printf ("%d\n", sol);
	
	if (sol > 1000) sol = 1000;
	for (i = 1; i <= sol; i++)
		printf ("%d ", V[i]);
	return 0;
}