Cod sursa(job #547680)

Utilizator Eugen01Vasilescu Eugen Eugen01 Data 6 martie 2011 17:01:45
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 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;
	for (i=1;i<n;i++)
	{
		if (s1[i]==s1[q])
			q++;
			else q=0;
		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;
	while (i<=m)
	{
		if (q==0||s2[i]==s1[q])
			q++,i++;
		else 
				q=a[q-1];
		if (q==n)
		{
			q=a[q-1];
			nr++;
			if (nr<=1000) b[nr]=i-n;
		}
	}
	printf("%d\n",nr);
	if (nr>1000) nr=1000;
	
	for (i=1;i<=nr;i++)
		printf("%d ",b[i]);
	printf("\n");
	
	return 0;
}