Cod sursa(job #361597)

Utilizator funkydvdIancu David Traian funkydvd Data 5 noiembrie 2009 22:37:48
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <stdio.h>
#include <algorithm>
#define MAXN 2000010
char a[MAXN], b[MAXN];
int pi[MAXN], poz[1002];
int i,n,m,sol,q;
void prefix()
{
	int i,q=0;
	pi[1]=0;
	for (i=2; i<=n; i++)
	{
		while (q && a[q+1]!=a[i]) q=pi[q];
		if (a[q+1]==a[i]) q++;
		pi[i]=q;
	}
}
int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	fgets(a,MAXN,stdin);
	fgets(b,MAXN,stdin);
	n=strlen(a); m=strlen(b);
	for(i=n; i>=1; i--) a[i]=a[i-1]; 
	for(i=m; i>=1; i--) b[i]=b[i-1];
	a[0]=b[0]=' '; n--;
	prefix();
	q=sol=0;
	for (i=1; i<=m; i++)
	{
		while (q && a[q+1]!=b[i]) q=pi[q];
		if (a[q+1]==b[i])  q++;
		if (q==n)
		{
			sol++;
			if (sol<1001)  poz[sol]=i-n;
			q=pi[q];
		}
	}
	printf("%d\n",sol);
	if (sol>1000) sol=1000;
	for (i=1; i<=sol; i++)
		printf("%d ",poz[i]);
	printf("\n");
	return 0;
}