Cod sursa(job #1110293)

Utilizator gener.omerGener Omer gener.omer Data 17 februarie 2014 22:17:11
Problema Potrivirea sirurilor Scor 18
Compilator c Status done
Runda Arhiva educationala Marime 0.86 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 && b[i-1] != b[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) {
		if(s2[i] == s1[j]) {
			++j;
			if(j == n1) {
				sol[all++] = i - n1 + 1;
				if(all == 1000) 
					break;
				j = b[j];
				++j;
			}
		}
		else {
			while(j >= 0 && s1[j] != s2[i]) 
				j = b[j];
			++j;
		}
	}
	
	printf("%d\n", all);
	for(i = 0; i < all; ++i)
		printf("%d ", sol[i]);
	
	return 0;
}