Cod sursa(job #496659)

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

long M1,M2,B,cod1,cod2,sir1,sir2,n,m,i,pow1,pow2,sol,v[1002],ok[255];
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;
	for(i=0;i<=n;i++)
		if(ok[a[i]]==0)
		{
			B++;
			ok[a[i]]=1;
		}
			
	for(i=0;i<=m;i++)
		if(ok[b[i]]==0)
		{
			B++;
			ok[b[i]]=1;
		}
			

	B++;
	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=0;
	if(cod1==sir1&&cod2==sir2)
	{
		sol++;
		if(sol<=1000) v[sol]=0;
	}
	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++;
			
		}
	}
	printf("%ld\n",sol);
	if(sol>1000) sol=1000;
	for(i=1;i<=sol;i++)
		printf("%ld ",v[i]);
	printf("\n");

	return 0;
}