Cod sursa(job #397985)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 17 februarie 2010 20:01:38
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <cstdio>
#include <cstring>

#define file_in "strmatch.in"
#define file_out "strmatch.out"

#define Nmax 2312332

int i,nr,k,pi[Nmax],sir[Nmax],n,m;
char a[Nmax],b[Nmax];

int main()
{
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%s\n", a+1);
	n=strlen(a+1);
	scanf("%s\n", b+1);
	m=strlen(b+1);
	
	k=0;
	pi[1]=0;
	
	for (i=2;i<=n;++i)
	{
		while(k>0 && a[i]!=a[k+1]) k=pi[k];
		if (a[i]==a[k+1]) k++;
		pi[i]=k;
	}
	
	k=0;
	nr=0;
	for (i=1;i<=m;++i)
	{
		while(k>0 && b[i]!=a[k+1]) k=pi[k];
		if (b[i]==a[k+1]) k++;
		if (k==n)
		{
			nr++;
			sir[nr]=i-n;
		}
	}
	
	printf("%d\n", nr);
	for (i=1;i<=nr && i<=1000;++i)
		 printf("%d ", sir[i]);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}