Cod sursa(job #170041)

Utilizator za_wolfpalianos cristian za_wolf Data 2 aprilie 2008 12:43:49
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include<stdio.h>
#include<string.h>
#define NMAX 2000010
#define MMAX 1010
int q,s[MMAX];
void prekmp(char *x, int m, int k[])
{
	int i,j;
	i=0;
	j=k[0]=-1;
	while (i<m)
	{
		while (j>-1&&x[i]!=x[j])
			j=k[j];
		i++, j++;
		if (x[i]==x[j])
			k[i]=k[j];
		else
			k[i]=j;
	}
}

void kmp(char *x, int m, char *y, int n)
{
	int i,j,k[NMAX];
	prekmp(x,m,k);
	i=j=0;
	while (i<n)
	{
		while(j>-1&&x[j]!=y[i])
			j=k[j];
		i++,j++;
		if (j>=m)
		{
			q++;
			if (q<=1000)
				s[q]=i-j;
			j=k[j];
		}
	}
}

void afis()
{
	printf("%d\n",q);
	for (int i=1;i<=q&&i<=1000;i++)
		printf("%d ",s[i]);
	printf("\n");
}

int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	int n,m;
	char a[NMAX],b[NMAX];
	gets(a);
	gets(b);
	m=strlen(a);
	n=strlen(b);

	kmp(a,m,b,n);

    afis();
	return 0;
}