Cod sursa(job #704519)

Utilizator Anonymous1010Chilivercu Cristian Anonymous1010 Data 2 martie 2012 18:30:51
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<stdio.h>
#include<string.h>

char a[2000005],c;
int n,b[1002],pi[2000005],m,i,q,min,max;

void make_prefix();

int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	
	scanf("%s\n",a);
	
	n=strlen(a);
	pi[0]=-1;
	pi[1]=-1;
	q=-1;
	max=n-1;
	
	make_prefix();
	
	for(i=0,q=-1;!feof(stdin);i++)
	{
		scanf("%c",&c);
		
		for(;q!=-1&&a[q+1]!=c;)
			q=pi[q];
		
		
		if(a[q+1]==c)
			q++;
		
		if(q==max)
		{
			q=pi[max];
			m++;
			if(m<=1000)
				b[m]=i-max;
		}
	}
	
	printf("%d\n",m);
	
	if(m<=1000)
		min=m;
	else
		min=1000;
	
	for(i=1;i<=min;i++)
		printf("%d ",b[i]);
	
	return 0;
}

void make_prefix()
{
	for(i=1;i<n;i++)
	{
		for(;q!=-1&&a[q+1]!=a[i];)
			q=pi[q];
		
		if(a[q+1]==a[i])
			q++;
		pi[i]=q;
	}
}