Cod sursa(job #496451)

Utilizator ZethpixZethpix Zethpix Data 29 octombrie 2010 10:06:16
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <stdio.h>
#include <string.h>

struct point
{
	long nod;
	point *link;
}*q;

struct hash
{
	long nod;
	long nr;
	point *list;
	hash *link;
}*H[1000000],*p;

long val,c,n,m,i,C,pos;
char a[2000002],b[2000002];

void add(long x,long pos,long i)
{
	hash *p;
	point *q;
	long nr=0;

	if(pos==0)
	{
		p=new hash;
		p->nod=i;
		p->nr=1;
		q=new point;
		q->nod=i;
		q->link=p->list;
		p->list=q;
		p->link=H[x%C];
		H[x%C]=p;
	}
	else
	{
		p=H[x%C];
		for(nr=1;nr<=pos;nr++) p=p->link;
		p->nr++;
		q=new point;
		q->nod=i;
		q->link=p->list;
		p->list=q;
	}
}

long src(long x,long pos)
{
	hash *p;
	p=H[x%C];
	long nr=0;
	while(p!=NULL)
	{
		if(p->nod==pos) return nr;
		nr++;
		p=p->link;
	}
	return 0;
}

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

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

	val=0;
	C=999983;
	n=strlen(a)-1;
	if(a[n]=='\n') n--;
	m=strlen(b)-1;
	if(b[m]=='\n') m--;
	for(i=0;i<=n;i++)
		val+=b[i];
	add(val,0,0);
	for(i=n+1;i<=m;i++)
	{
		val-=b[i-n];
		val+=b[i];
		pos=src(val,i);
		add(val,pos,i-n);
	}
	val=0;
	for(i=0;i<=n;i++)
		val+=a[i];
	p=H[val%C];
	while(p!=NULL)
	{
		if(p->nod==val)
		{
			printf("%ld\n",p->nr);
			q=p->list;
			val=0;
			while(q!=NULL&&val<=1000)
			{
				printf("%ld ",q->nod);
				val++;
				q=q->link;
			}
			printf("\n");
			return 0;
		}
		p=p->link;
	}
	return 0;
}