Cod sursa(job #152998)

Utilizator andrei.12Andrei Parvu andrei.12 Data 9 martie 2008 23:18:33
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include<stdio.h>
#include<string.h>
#include<algorithm>

using namespace std;

#define lg 2000001

char s1[lg], s2[lg], sr1[lg], sr2[lg];
int x1, x2, i, x, urm[lg], nr[1001], nrs;

void prefix(){
	int i, k = 0;

	for (i = 2; i <= x1; i ++){
		while (k > 0 && sr1[k+1] != sr1[i])
			k = urm[k];

		if (sr1[k+1] == sr1[i])
			k ++;
		urm[i] = k;
	}
}
int main()
{
	freopen("strmatch.in", "rt", stdin);
	freopen("strmatch.out", "wt", stdout);

	scanf("%s%s", s1, s2);
	
	x1 = strlen(s1);
	x2 = strlen(s2);

	for (i = 0; i < x1; i ++)
		sr1[i+1] = s1[i];
	for (i = 0; i < x2; i ++)
		sr2[i+1] = s2[i];

	prefix();
	
	for (i = 1; i <= x2; i ++){
		while (x > 0 && sr1[x+1] != sr2[i])
			x = urm[x];

		if (sr1[x+1] == sr2[i])
			x ++;
		if (x == x1){
			nrs ++;
			if (nrs <= 1000)
				nr[nrs] = i-x1;
		}
	}

	printf("%d\n", nrs);
	for (i = 1; i <= min(nrs, 1000); i ++)
		printf("%d ", nr[i]);
	printf("\n");

	return 0;
}