Cod sursa(job #919239)

Utilizator taigi100Cazacu Robert taigi100 Data 19 martie 2013 15:25:47
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include<stdio.h>
#include<string.h>
#define max 2000005

char pat[max],txt[max];
int pos[1069],pi[max],n,m;

void ComputePref()
{
	pi[1]=0;
	int i,q=0;
	for(i=2;i<=m;++i)
	{
		while( q && pat[q+1] != pat[i] )
			q=pi[q];
		if(pat[q+1] == pat[i])
			++q;
		pi[i]=q;
	}
}
int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	
	fgets(pat,sizeof(pat),stdin);
	fgets(txt,sizeof(txt),stdin);
	
    m=strlen(pat)-1;
	n=strlen(txt)-1;
	for(int i=m;i>=1;i--) pat[i]=pat[i-1]; pat[0]=' ';
	for(int i=n;i>=1;i--) txt[i]=txt[i-1]; txt[0]=' ';
	ComputePref();
	int q=0,z=0;
	for(int i=1;i<=n;++i)
	{
		while( q && pat[q+1] != txt[i])
			q=pi[q];
		if(pat[q+1]==txt[i])
			q++;
		if(q==m)
		{
			q=pi[m];
			z++;
			if(z<=1000)
				pos[z]=i-m;
		}
	}
	printf("%d\n",z);
	for(int i=1;i<= ( z<=1000 ? z : 1000 ); ++i)
		printf("%d ",pos[i]);
	printf("\n");
	return 0;
}