Cod sursa(job #548466)

Utilizator Eugen01Vasilescu Eugen Eugen01 Data 7 martie 2011 14:35:25
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<stdio.h>
#include<string.h>
#define Nmax 2000009 

int nr,q,i,j,n,m,a[Nmax],b[1000];
char s1[Nmax],s2[Nmax];

void prefix()
{
	q=0;
	a[0]=0;
	for (i=1;i<n;i++)
	{
		while (q>0&&s1[q]!=s1[i])
			q=a[q-1];
		if (s1[q]==s1[i])
			q++;
		a[i]=q;
	}
}


int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	
	gets(s1);
	gets(s2);
	
	n=strlen(s1);m=strlen(s2);
	prefix();
	
	q=0;i=0;
	
	for (i=0;i<m;i++)
	{
		while(q>0 && s1[q]!=s2[i])
			q=a[q-1];
		if(s1[q]==s2[i])
			q++;

		if (q==n)
		{
			q=a[q-1];
			nr++;
			if (nr<=1000) b[nr]=i-n+1;
		}
	}

	printf("%d\n",nr);
	if (nr>1000) nr=1000;
	
	for (i=1;i<=nr;i++)
		printf("%d ",b[i]);
	printf("\n");
	
	return 0;
}