Cod sursa(job #270478)

Utilizator BaduBadu Badu Badu Data 4 martie 2009 01:13:15
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include<stdio.h>
#include<string.h>

char A[2000000],B[2000000];
int P[2000001],S[1001],n,m,cat;

int main(){

	freopen("strmach.in","rt",stdin);
	freopen("strmach.out","wt",stdout);

	gets(A);
	gets(B);

	int k,i;

	n = strlen(A);
	for(i=n;i>0;i--)A[i]=A[i-1];
	m = strlen(B);
	for(i=m;i>0;i--)B[i]=B[i-1];


	k=0;
	P[1]=0;

	for(i=2;i<=n;i++){

		while(k>0 && A[k+1]!=A[i]) k = P[k];

		if(P[k+1] == P[i]) k++;

		P[i] = k;

	}

	k = 0;

	for(i=1;i<=m;i++){

		while(k>0 && A[k+1]!=B[i]) k = P[k];

		if(A[k+1] == B[i]) k++;

		if(k == n) {

			cat++;

			if(cat<1001) S[cat]=i-n;

			k = P[k];

		}
	}

	printf("%d\n",cat);



	cat = cat>1000?1000:cat;

	for(i=1;i<=cat;i++) printf("%d ",S[i]);

	return 0;

}