Cod sursa(job #361570)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 5 noiembrie 2009 21:04:54
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <stdio.h>
#include <algorithm>
#define MAXN 2010

char a[MAXN], b[MAXN];
int pi[MAXN], poz[1024];
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--; m--;
	
	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;
}