Cod sursa(job #854601)

Utilizator radustn92Radu Stancu radustn92 Data 13 ianuarie 2013 19:31:57
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <cstdio>
#include <cstring>
#define NMAX 2000005
#define LMAX 4000005
#define HMAX 1005
int n,m,r,C[LMAX],res,sol[HMAX];
char A[LMAX];

void read()
{
	fgets(A+1,NMAX,stdin);
	n=strlen(A+1)-1; 
	fgets(A+n+1,NMAX,stdin);
	m=strlen(A+n+1)-1;
}

inline int min(int x,int y)
{
	return x<y ? x : y;
}

void solve()
{
	int i,left,right,pos;
	left=right=-1;
	for (i=2; i<=n+m; i++)
	{
		if (right<i)
		{
			if (A[i]==A[1])
			{
				left=right=i;
				while (right+1<=n+m && A[right+1]==A[right-left+2])
					right++;
				C[i]=right-left+1;
			}
			continue ;
		}
		
		pos=i-left+1;
		if (i+C[pos]-1<right)
		{
			C[i]=C[pos];
			continue ;
		}
		
		left=i;
		while (right+1<=n+m && A[right+1]==A[right-left+2])
			right++;
		C[i]=right-left+1;
	}
	
	for (i=n+1; i<=n+m; i++)
		if (C[i]>=n)
		{
			res++;
			if (res<=1000)
				sol[res]=i-n-1;
		}
		
	
	printf("%d\n",res);
	for (i=1,res=min(res,1000); i<=res; i++)
		printf("%d ",sol[i]);
	printf("\n");
}

int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	read();
	solve();
	return 0;
}