Cod sursa(job #270464)

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

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

int main(){

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

	gets(A);
	gets(B);

	n = strlen(A);
	m = strlen(B);

	int k,i;

	k=-1;
	P[0]=0;

	for(i=1;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 = -1;

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

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

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

		if(k == n-1) {

			cat++;

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

		}
	}

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

	cat = cat>1000?1000:cat;

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

	return 0;

}