Cod sursa(job #1110288)

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

#define NMAX 2000005

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

void preprocess() {
	unsigned i;
	int j = -1;
	b[0] = -1;
	for(i = 1; i <= strlen(s1); ++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);
	preprocess();
	unsigned i;
	int	j;
	for(i = 0, j = 0; i < strlen(s2); ++i) {
		if(s2[i] == s1[j]) {
			++j;
			if(j == strlen(s1)) {
				sol[all++] = i - strlen(s1) + 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;
}