Cod sursa(job #491072)

Utilizator snycwingsnycwing snycwing Data 9 octombrie 2010 16:28:06
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <stdio.h>
#include <string.h>

int b,i,p,t,ok[130],sol,key,nr,j,pow,v,w[1002],m;
char P[2000002],T[2000002];

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

	fgets(P,2000002,stdin);
	fgets(T,2000002,stdin);

	p=strlen(P)-1;
	if(P[p]=='\n') p--;
	t=strlen(T)-1;
	if(T[t]=='\n') t--;

	for(i='0';i<='z';i++) ok[i]=0;
	b=0;
	for(i=0;i<=t;i++)
		if(ok[T[i]-'0']==0)
		{
			b++;
			ok[T[i]-'0']=1;
		}

	m=29837;
	sol=0;
	key=0;
	pow=1;
	b++;
	for(i=p;i>=0;i--)
	{
		key+=pow*(P[i]-'0');
		key%=m;
		pow*=b;
		pow%=m;
	}

	nr=0;
	pow=1;
	for(i=p;i>0;i--)
	{
		nr+=pow*(T[i]-'0');
		nr%=m;
		pow*=b;
		pow%=m;
	}
	nr+=pow*(T[0]-'0');
	nr%=m;

	v=0;
	for(j=0;j<=p;j++)
		if(T[j]!=P[j])
		{
			v=1;
			break;
		}
	if(v==0)
	{
		sol++;
		if(sol<=1000) w[sol]=0;
	}

	for(i=p+1;i<=t;i++)
	{
		nr-=pow*(T[i-p-1]-'0');
		if(nr<0) nr+=m;
		nr*=b;
		nr+=T[i]-'0';
		nr%=m;
		if(nr==key)
		{
			v=0;
			for(j=0;j<=p;j++)
				if(T[j+i-p]!=P[j])
				{
					v=1;
					break;
				}
			if(v==0)
			{
				sol++;
				if(sol<=1000) w[sol]=i-p;
			}
		}
	}
	printf("%d\n",sol);
	if(sol>1000) sol=1000;
	for(i=1;i<sol;i++)
		printf("%d ",w[i]);
	if(sol!=0) printf("%d\n",w[sol]);

	return 0;
}