Cod sursa(job #779635)

Utilizator crushackPopescu Silviu crushack Data 18 august 2012 13:53:58
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <stdio.h>
#include <string.h>
#define NMax 2000010
const char IN[]="strmatch.in",OUT[]="strmatch.out";

int N,M;
int P[NMax],Rez[1010];
char A[NMax],B[NMax];

void prefix(){

	int i,k=0;
	P[1]=k;
	for (i=2;i<=N;++i)
	{
		while (k>0 && A[k+1]!=A[i])
			k=P[k];
		if (A[k+1]==A[i])
			++k;
		P[i]=k;
	}
}

void solve(){

	int i,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)
		{
			++Rez[0];
			if (Rez[0]>1000) continue;
			Rez[Rez[0]]=i-N;
		}
	}

}

int main()
{
	int i;
	freopen(IN,"r",stdin);
	scanf("%s%s",A+1,B+1);
	fclose(stdin);

	N=strlen(A+1);M=strlen(B+1);
	prefix();
	solve();

	freopen(OUT,"w",stdout);
	printf("%d\n",Rez[0]);
	for (i=1;i<=Rez[0] && i<1001;++i) printf("%d ",Rez[i]); printf("\n");
	fclose(stdout);

	return 0;
}