Cod sursa(job #416670)

Utilizator matemariaescuMaria Mateescu matemariaescu Data 13 martie 2010 10:55:58
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
# include <stdio.h>
# include <string.h>

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

int main ()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);

	T[0] = P[0] = ' ';
	scanf("%s\n",&P[1]);
	scanf("%s",&T[1]);
	m=strlen(P)-1;
	n=strlen(T)-1;
	//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;
}