Cod sursa(job #303305)

Utilizator AndreyPAndrei Poenaru AndreyP Data 9 aprilie 2009 18:58:58
Problema Potrivirea sirurilor Scor 26
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include<stdio.h>
#define N 2000010
char a[N],b[N];
int pi[N],v[1005],la,lb;
int strlen(char c[N])
{
	int i;
	for(i=1; c[i]!='\0'; ++i)
		;
	--i;
	if(c[i]=='\n')
		--i;
	return i;
}
inline void precalc()
{
	int q=0;
	pi[1]=0;
	for(int i=2; i<=la; ++i)
	{
		while(q>0 && a[i]!=a[q+1])
			q=pi[q];
		if(a[i]==a[q+1])
			++q;
		pi[i]=q;
	}
}
inline void rezolva()
{
	int q=0;
	for(int i=1; i<=lb; ++i)
	{
		while(q>0 && b[i]!=a[q+1])
			q=pi[q];
		if(b[i]==a[q+1])
			++q;
		if(q==la && v[0]<1000)
			v[++v[0]]=i-la;
	}
	printf("%d\n",v[0]);
	for(int i=1; i<v[0]; ++i)
		printf("%d ",v[i]);
	printf("%d\n",v[v[0]]);
}
int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	fgets(a+1,N,stdin);
	fgets(b+1,N,stdin);
	la=strlen(a);
	lb=strlen(b);
	precalc();
	rezolva();
	return 0;
}