Cod sursa(job #416664)

Utilizator matemariaescuMaria Mateescu matemariaescu Data 13 martie 2010 10:47:38
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
# include <stdio.h>

char P[2000000], T[2000000];
int L[2000000];
int v[1001];
int sol,p,t,k,m,n;
char ch;

int main ()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	scanf("%c",&ch);
	while (ch!='\n')
	{
		m++;
		P[m]=ch;
		scanf("%c",&ch);
	}
	scanf("%c",&ch);
	while (ch!='\n')
	{
		n++;
		T[n]=ch;
		scanf("%c",&ch);
	}
	//calculez L
	L[1]=0;
	for (p=2;p<=m;p++)
	{
		k=L[p-1];
		while (k>0 && P[k+1]!=P[p])
			k=L[k];
		if (P[k+1]==P[p])
			k++;
		L[p]=k;
	}
	// pirima oara numar
	k=0;
	for (t=1;t<=n;t++)
	{
		while (k>0 && P[k+1]!=T[t])
			k=L[k];
		if (P[k+1]==T[t])
			k++;
		if (k==m)
		{
			sol++;
			if (sol<=1000)
				v[sol]=t-m;
			k=L[k];
		}
	}
	printf("%d\n",sol);
	if (sol>1000)
		sol=1000;
	for (k=1;k<=sol;k++)
		printf("%d ",v[k]);
	printf("\n");
	return 0;
}