Cod sursa(job #278211)

Utilizator vladbBogolin Vlad vladb Data 12 martie 2009 10:11:24
Problema Potrivirea sirurilor Scor 36
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<stdio.h>
#include<string.h>

char n[2000000],m[2000000];
long N,M;
int pi[2000000],x[1005],c;

void pref()
{   int i,k;
	N=strlen(n);
	k=0;
	pi[1]=0;
	for(i=2;i<=N;i++)
	{	while(k>0&&n[k+1]!=n[i])
			k=pi[k];
		if(n[k+1]==n[i])
			k+=1;
		pi[i]=k;
	}
}

void kmp()
{   int q,i;
	M=strlen(m);
	q=0;
	pref();
	for(i=1;i<M;i++)
	{	while(q>0&&n[q+1]!=m[i])
			q=pi[q];
		if(n[q+1]==m[i])
			q+=1;
		if(q==N-1)
		{	c++;
		  if(c<=1000)
			x[c]=i-N+1;
		}
	}
}

int main()
{   freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	scanf("%s",n);
	scanf("%s",m);
	kmp();
	printf("%d\n",c);
    if(c>1000) c=1000;
	for(int i=1;i<=c;i++)
    	printf("%d ",x[i]);
	return 0;
}