Cod sursa(job #1110314)

Utilizator gener.omerGener Omer gener.omer Data 17 februarie 2014 22:53:40
Problema Potrivirea sirurilor Scor 20
Compilator c Status done
Runda Arhiva educationala Marime 0.81 kb
#include <stdio.h>
#include <string.h>

#define NMAX 2000005

char s1[NMAX], s2[NMAX];
int b[NMAX];

int n1, n2;

void preprocess() {
	unsigned i;
	int j = -1;
	b[0] = -1;
	for(i = 1; i <= n1; ++i) {
		while(j >= 0 && s1[i-1] != s1[j]) 
			j = b[j];
		b[i] = ++j;
	}
}

int sol[1001], all = 0;

int main()
{
	freopen("strmatch.in", "rt", stdin);
	freopen("strmatch.out", "wt", stdout);
	scanf("%s", s1); scanf("%s", s2);
	n1 = strlen(s1), n2 = strlen(s2);
	preprocess();
	unsigned i;

	int	j;
	for(i = 0, j = 0; i < n2; ++i) {
		while(j >= 0 && s1[j] != s2[i]) 
			j = b[j];
		++j;
		if(j == n1) {
			sol[all++] = i - n1 + 1;
			if(all == 1000) 
				goto print;
			j = b[j]; ++j;
		}
	}

print:	
	printf("%d\n", all);
	for(i = 0; i < all; ++i)
		printf("%d ", sol[i]);
	
	return 0;
}