Cod sursa(job #793915)

Utilizator MtkMarianHagrSnaf MtkMarian Data 4 octombrie 2012 18:14:58
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include<cstdio>
#include<string.h>
#include<cmath>
#define NMAX 2000005
char a[NMAX],b[NMAX];
int n,m;
unsigned int pi[NMAX],ret[1024];
void c_pi()
{
	int k=1;
	pi[1]=0;
	for(int i=2;i<=n;++i)
	{
		while( k>0 && a[i-1] != a[k+1] )k=pi[k];
		if(a[i]==a[k+1])++k;
		pi[i]=k;
	}
}



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

	
	

	fgets(a, sizeof(a), stdin);
	fgets(b, sizeof(b), stdin);

	for (n=0; (a[n] >= 'A' && a[n] <= 'Z') || (a[n] >= 'a' && a[n] <= 'z')|| (a[n] >= '0' && a[n] <= '9'); ++n);
	for (m=0; (b[m] >= 'A' && b[m] <= 'Z') || (b[m] >= 'a' && b[m] <= 'z')|| (b[m] >= '0' && b[m] <= '9'); ++m);
	for(int i=n;i>0;--i)a[i]=a[i-1];
	a[0]=' ';
	for (int i=m;i>0;--i)b[i]=b[i-1];
	b[0]=' ';
	c_pi();
	
	int q=0;
	int j=0;

	for(int i=1;i<=m;++i)
	{
		while(q>0 && b[i]!=a[q+1])
			q=pi[q];
		if(a[q+1]==b[i])++q;
		if( q == n)
		{
			q=pi[n];
			++j;
			if(j<=1000)	ret[j]=i-n;
			
			
		}
	}
	printf("%d\n",j);
	ret[++j]=-1;


	j=1;
	
	while(ret[j]!=-1)
	{
		printf("%d ",ret[j]);
		++j;
	}
	printf("\n");
	return 0;
}