Cod sursa(job #169933)

Utilizator AndreyPAndrei Poenaru AndreyP Data 2 aprilie 2008 11:07:35
Problema Potrivirea sirurilor Scor 26
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<stdio.h>
#include<string.h>
#define N 2000001
char a[N],b[N];
int pi[N],v[1001];
int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	int la,lb,k=0,n=0,i;
	scanf("%s",a+1);
	scanf("%s",b+1);
	la=strlen(a+1);
	lb=strlen(b+1);
	pi[1]=0;
	for(i=2; i<=la; i++)
	{
		while((k>0)&&(a[k+1]!=a[i]))
			k=pi[k];
		if(a[k+1]==a[i])
			k++;
		pi[i]=k;
	}
	int q=0;
	for(i=1; i<=lb; i++)
	{
		while((q>0)&&(a[q+1]!=b[i]))
			q=pi[q];
		if(a[q+1]==b[i])
			q++;
		if((q==la)&&(n<1000))
		{
			n++;
			v[n]=i-la;
		}
	}
	printf("%d\n",n);
	for(i=1; (i<n)&&(i<1000); i++)
		printf("%d ",v[i]);
	if(n>1000)
		n=1000;
	printf("%d\n",v[n]);
	return 0;
}