Cod sursa(job #270480)

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

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

int main(){

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

	scanf("%s\n",A);
	scanf("%s",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;

}