Cod sursa(job #362416)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 9 noiembrie 2009 16:48:30
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <cstdio>
#define lm 2000010
#define sm 1001
#include <cstring>

int n, m, pi[lm], r[sm];
char A[lm], B[lm];

void prefix()
{
	pi[1]=0;
	int i, k=0;
	for (i=2; i<=m; i++)
	{
		while (k && A[k+1]!=A[i]) k = pi[k];
		if (A[k+1]==A[i]) k++;
		pi[i]=k;
	}
}

int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	scanf("%s",A);
	scanf("%s",B);
	m=strlen(A);
	n=strlen(B);
	int i;
	for (i=m; i>0; i--) A[i]=A[i-1];
	for (i=n; i>0; i--) B[i]=B[i-1];
	prefix();
	int k=0, s=0;
	for (i=1; i<=n; i++)
	{
		while (k && A[k+1]!=B[i]) k=pi[k];
		if (A[k+1]==B[i]) k++;
		if (k==m)
		{
			s++;
			if (s<sm) r[s]=i-m;
		}
	}
	printf("%d\n",s);
	if (s>=sm) s=sm-1;
	for (i=1; i<=s; i++) printf("%d ",r[i]);
}