Cod sursa(job #507953)

Utilizator ZethpixZethpix Zethpix Data 7 decembrie 2010 09:27:01
Problema Potrivirea sirurilor Scor 52
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <stdio.h>
#include <string.h>

int m,n,i,k,L[2000005],v[1002],sol=0;
char Str[2000005],Pat[2000005];

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

	fgets(Pat+1,2000005,stdin);
	fgets(Str+1,2000005,stdin);

	Pat[0]='!';
	Str[0]='!';
	m=strlen(Pat)-1;
	n=strlen(Str)-1;
	if(Pat[m]=='\n') m--;
	if(Str[n]=='\n') n--;

	for(i=1;i<=102;i++) L[i]=0;
	L[1]=0;
	for(i=2;i<=m;i++)
	{
		while(k>0&&Pat[k+1]!=Pat[i]) k=L[k];
		if(Pat[k+1]==Pat[i]) k++;
		L[i]=k;
	}

	sol=0;
	for(i=1;i<=n;i++)
	{
		while(k>0&&Str[i]!=Pat[k+1]) k=L[k];
		if(Pat[k+1]==Str[i]) k++;
		if(k==m)
		{
			sol++;
			if(sol<=1000) v[sol]=i-k;
			k=L[k];
		}
	}
 	printf("%d\n",sol);
	if(sol>1000) sol=1000;
	for(i=1;i<=sol;i++)
		printf("%d ",v[i]);
	printf("\n");

	return 0;
}