Cod sursa(job #172004)

Utilizator andreisfrentSfrent Andrei andreisfrent Data 5 aprilie 2008 16:49:10
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <stdio.h>
#include <string.h>

#define maxN 2000005

char a[maxN], b[maxN];
int p[maxN];
int na, nb;

void calcul_prefix()
{
	int k, i;
	k = 0;
	p[1] = 0;
	for(i=2; i<=na; ++i)
	{
		while(k>0 && (a[k+1] != a[i]))
			k = p[k];
		if(a[k+1]==a[i]) k++;
		p[i]=k;		
	}
}

int main()
{
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	scanf("%s\n", a + 1);
	scanf("%s\n", b + 1);
	fclose(stdin);
	na = strlen(a+1);
	nb = strlen(b+1);
	calcul_prefix();
	int idx[maxN], q=0, cnt=0, i;
	for(i=1;i<=nb;++i)
	{
		while((q>0) && (a[q+1] != b[i]))
			q=p[q];
		if(a[q+1]==b[i])
			q++;
		if(q==na)
		{
			idx[++cnt] = nb-i+1;
		}
	}
	printf("%d\n",cnt);
	if(cnt>1000) cnt=1000;
	for(i=1;i<=cnt;++i) printf("%d ", idx[i]);
	printf("\n");
	fclose(stdout);
	return 0;
}