Cod sursa(job #704444)

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

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

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=0;
	
	make_prefix();
	
	for(i=0;!feof(stdin);i++)
	{
		scanf("%c",&c);
		
		for(;q>=0&&a[q+1]!=c;)
			q=pi[q];
		
		
		if(a[q+1]==c)
			q++;
		
		if(q==n-1)
		{
			q=pi[n];
			m++;
			if(m<=1000)
				b[m]=i-n;
		}
	}
	
	printf("%d\n",m);
	
		if(m<=1000)
			min=m;
		else
			min=1000;
	
	for(i=1;i<=min;i++)
		printf("%d ",b[i]+1);
	
	return 0;
}

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