Cod sursa(job #681546)

Utilizator ciprianfFarcasanu Alexandru Ciprian ciprianf Data 17 februarie 2012 12:20:44
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <stdio.h>
#define N_MAX 2000010
char A[N_MAX], B[N_MAX];
int pi[N_MAX];
int sol[1005];
int n;
void precalc() {
	pi[1] = 0;
	int k = 0;
	for(int i = 2; A[i] != '\n' && A[i]; i++) {
		while(k > 0 && A[k+1] != A[i]) {
			k = pi[k];
		}
		if(A[k+1] == A[i]) {
			k++;
		}
		pi[i] = k;
		n = i;
	}	
}

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