Cod sursa(job #496542)

Utilizator ZethpixZethpix Zethpix Data 29 octombrie 2010 17:48:42
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 kb
#include <stdio.h>
#include <string.h>

struct hash
{
	long nod,val;
	hash *link;
}*H[1000000];

char a[2000002],b[2000002];
long n,m,B,M,i,sir,aux,pow,nr,v[1002];

void add(long x,long pos)
{
	hash *p;
	p=new hash;
	p->nod=x;
	p->val=pos;
	p->link=H[x%M];
	H[x%M]=p;
}

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

long src(long x,long ok)
{
	hash *p,*q;
	q=NULL;
	p=H[x%M];
	while(p!=NULL)
	{
		if(p->nod==x)
		{
			if(ok==0) return p->val;
			else
			if(ver(p->val))
			{
				if(q==NULL&&p->link==NULL) H[x%M]=NULL;
				else
				if(q==NULL&&p->link!=NULL)
					H[x%M]=p->link;
				else
				if(p->link!=NULL) q->link=p->link;
				else
				q->link=NULL;
				return p->val;
			}
		}
		if(ok==1) q=p;
		p=p->link;
	}
}

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--;
	M=999983;
	B=0;
	for(i=0;i<=n;i++)
	{
		aux=src(a[i],0);
		if(aux==0)
		{
			add(a[i],++B);
			a[i]=B;
		}
		else a[i]=aux;
	}

	for(i=0;i<=m;i++)
	{
		aux=src(b[i],0);
		if(aux==0)
		{
			add(b[i],++B);
			b[i]=B;
		}
		else b[i]=aux;
	}

	for(i=1;i<=M;i++) H[i]=NULL;
	pow=1;
	sir=0;
	for(i=n;i>=0;i--)
	{
		sir+=pow*b[i];
		sir%=M;
		pow*=B;
		pow%=M;
	}
	add(sir,0);
	for(i=n+1;i<=m;i++)
	{
		sir*=B;
		sir+=b[i];
		sir-=pow*b[i-n-1];
		sir%=M;
		add(sir,i-n);
	}
	pow=1;
	sir=0;
	for(i=n;i>=0;i--)
	{
		sir+=pow*a[i];
		sir%=M;
		pow*=B;
		pow%=M;
	}
	aux=src(sir,1);
	nr=0;
	while(aux!=0)
	{
		v[++nr]=aux;
		if(nr>1000) break;
		aux=src(sir,1);
	}
	printf("%ld\n",nr);
	for(i=1;i<=nr;i++)
		printf("%ld ",v[i]);
	if(nr>0) printf("\n");

	return 0;
}