Cod sursa(job #496643)

Utilizator ZethpixZethpix Zethpix Data 30 octombrie 2010 09:41:54
Problema Potrivirea sirurilor Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <stdio.h>
#include <string.h>

long M,B,cod,sir,n,m,i,pow,sol,v[1002],ok[255];
char a[2000002],b[2000002];

long ver(long x)
{
	long i;
	for(i=x;i<=x+n;i++)
		if(a[i-x]!=b[i]) return 0;
	return 1;
}

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--;

	sir=0;
	cod=0;
	B=0;
	M=999983;
	for(i=0;i<=n;i++)
	{
		if(ok[a[i]]==0)
			ok[a[i]]=++B;
		a[i]=ok[a[i]];
	}
	for(i=0;i<=m;i++)
	{
		if(ok[b[i]]==0)
			ok[b[i]]=++B;
		b[i]=ok[b[i]];
	}

	pow=1;
	for(i=n;i>=0;i--)
	{
		sir+=a[i]*pow;
		sir%=M;
		pow*=B;
		pow%=M;
	}
	pow=1;
	for(i=n;i>=0;i--)
	{
		cod+=b[i]*pow;
		cod%=M;
		pow*=B;
		pow%=M;
	}
	sol=0;
	if(cod==sir)
		if(ver(0))
		{
			sol++;
			if(sol<=1000) v[sol]=0;
		}
	for(i=n+1;i<=m;i++)
	{
		cod*=B;
		cod-=pow*b[i-n-1];
		cod+=b[i]+M;
		cod%=M;
		if(cod==sir)
			if(ver(i-n))
			{
				sol++;
				if(sol<=1000) v[sol]=i-n;
			}
	}
	printf("%ld\n",sol);
	if(sol>1000) sol=1000;
	for(i=1;i<=sol;i++)
		printf("%ld ",v[i]);
	printf("\n");

	return 0;
}