Cod sursa(job #176189)

Utilizator alex_mircescuAlex Mircescu alex_mircescu Data 10 aprilie 2008 20:32:06
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <stdio.h>
#include <string.h>
#include <math.h>

#define MAX 2000010

long n, m, pi[MAX], i, k, nr, store[1000];
char A[MAX], B[MAX];


int main() {
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	scanf("%s\n %s\n", A + 1, B + 1);

	n = strlen(A + 1);
	m = strlen(B + 1);

	pi[1] = 0; 
	k = 0;
	for (i = 2; i <= n; ++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 <= m; ++i) {
		while (A[k + 1] != B[i] && k > 0) {
			k = pi[k];
		}
		if (A[k + 1] == B[i]) {
			++k;
		}
		if (k == n) {
			++nr;
			if (store[0] < 1000) {
				store[++store[0]] = i - n;
			}
		}
	}

	printf("%ld\n", nr);
	for (i = 1; i <= store[0]; ++i) {
		printf("%ld ", store[i]);
	}
	return 0;
}