Cod sursa(job #496674)

Utilizator ZethpixZethpix Zethpix Data 30 octombrie 2010 11:26:40
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <stdio.h>
#include <string.h>

long M1,M2,B,cod1,cod2,sir1,sir2,n,m,i,pow1,pow2,sol;
int v[2000002];
char a[2000002],b[2000002];

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

	fgets(a,2000002,stdin);
	fgets(b,2000002,stdin);
	n=strlen(a)-1;
	if(a[n]=='\n') n--;
	m=strlen(b)-1;
	if(b[m]=='\n') m--;

	sir1=0;
	cod1=0;
	sir2=0;
	cod2=0;
	B=0;
	M1=999983;
	M2=999961;

	B=67;
	for(i=0;i<=n;i++)
	{
		sir1=(sir1*B+a[i])%M1;
		sir2=(sir2*B+a[i])%M2;
	}
	for(i=0;i<=n;i++)
	{
		cod1=(cod1*B+b[i])%M1;
		cod2=(cod2*B+b[i])%M2;
	}
	pow1=1;
	pow2=1;
	for(i=0;i<n;i++)
	{
		pow1=(pow1*B)%M1;
		pow2=(pow2*B)%M2;
	}
	sol=1;
	if(cod1==sir1&&cod2==sir2)
	{
		sol++;
		v[0]=1;
	}
	for(i=n+1;i<=m;i++)
	{
		cod1=(cod1+M1-(b[i-n-1]*pow1)%M1)%M1;
		cod1=(cod1*B+b[i])%M1;
		cod2=(cod2+M2-(b[i-n-1]*pow2)%M2)%M2;
		cod2=(cod2*B+b[i])%M2;
		if(cod1==sir1&&cod2==sir2)
		{
			sol++;
			v[i-n]=1;
		}
	}
	printf("%ld\n",sol);
	sol=0;
	i=0;
	while(sol<=1000&&i<=m)
	{
		if(v[i])
		{
			printf("%ld ",i);
			sol++;
		}
		i++;
	}
	printf("\n");

	return 0;
}