Cod sursa(job #561220)

Utilizator blastoiseZ.Z.Daniel blastoise Data 19 martie 2011 07:49:06
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <stdio.h>
#include <string.h>

#define Dim 2000010

int M,N,i,k,sol;
int L[Dim],v[1002];
char S[Dim],P[Dim];

int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);

	fgets(P+1,Dim,stdin);
	fgets(S+1,Dim,stdin);
	P[0]='!';
	S[0]='!';
	M=strlen(P)-1;
	if(P[M]=='\n') P[M--]='\0';
	N=strlen(S)-1;
	if(S[N]=='\n') S[N--]='\0';

	memset(L,0,sizeof(L));

	k=0;
	L[1]=0;
	for(i=2;i<=M;i++)
	{
		while(k>0&&P[k+1]!=P[i]) k=L[k];
		if(P[k+1]==P[i]) k++;
		L[i]=k;
	}

	sol=0;
	memset(v,0,sizeof(v));
	k=0;

	for(i=1;i<=N;i++)
	{
		while(k>0&&P[k+1]!=S[i]) k=L[k];
		if(P[k+1]==S[i]) k++;
		if(k==M)
		{
			sol++;
			if(sol<1001) v[sol]=i-k;
			k=L[k];
		}
	}

	printf("%d\n",sol);
	if(sol>1000) sol=1000;
	for(i=1;i<=sol;i++)
		printf("%d ",v[i]);
	printf("\n");

	return 0;
}