Cod sursa(job #549238)

Utilizator tiriplicamihaiTiriplica Mihai Dragos tiriplicamihai Data 8 martie 2011 11:47:32
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <cstdio>
#include <string.h>

#define MaxN 2000010

char N[MaxN],M[MaxN];

int n,m,pi[MaxN],Nr,s[1001];

void cit()
{
	scanf("%s",&N);
	n=strlen(N);
	scanf("%s",&M);
	m=strlen(M);
}

void translatie()
{
	int i;
	for(i=n-1;i>=0;i--)
		N[i+1]=N[i];
	for(i=m-1;i>=0;i--)
		M[i+1]=M[i];
}

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

void kmp()
{
	int i,q=0;
	for(i=1;i<=m;i++)
	{
		while(q>0 && N[q+1]!=M[i])
			q=pi[q];
		if(N[q+1]==M[i])
			q++;
		if(q==n)
		{
			Nr++;
			if(Nr<=1000)
				s[Nr]=i-n+1;
		}
	}
}

int minim(int a,int b)
{
	return (a<b)? a:b;
}

void afis()
{
	printf("%d\n",Nr);
	int min=minim(Nr,1000);
		for(int i=1;i<=min;i++)
		{
			printf("%d ",s[i]-1);
		}
}

int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	cit();
	translatie();
	prefix();
	kmp();
	afis();
	fclose(stdin);
	fclose(stdout);
	return 0;
}