Cod sursa(job #316771)

Utilizator Alexa_ioana_14Antoche Ioana Alexandra Alexa_ioana_14 Data 21 mai 2009 08:25:33
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include<stdio.h>
#define N 2000005
char a[N],b[N];
int n,m,num,v[1001],p[N],k;
void pi()
{
	p[1]=0;
	k=0;
	for (int i=2; i<=n; ++i)
	{
		while (k&&a[k+1]!=a[i])
			k=p[k];
		if (a[k+1]==a[i]) ++k;
		p[i]=k;
	}
}
void kmp()
{
	k=0;
	for (int i=1; i<=m; ++i)
	{
		while (k&&a[k+1]!=b[i])
			k=p[k];
		if (a[k+1]==b[i])++k;
		if (k==n)
		{
			++num;
			if (num<=1000)
				v[num]=i-n;
			k=p[n];
		}
	}
}
void afis()
{
	printf("%d\n",num);
	for (int i=1; i<=num; ++i)
	{
		printf("%d ",v[i]);
		if (i>=1000)
			return;
	}
}
void citire()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	fgets(a,N-1,stdin);
	fgets(b,N-1,stdin);
	while (a[n])++n;--n;
	while (b[m])++m; --m;
	for (int i=n; i; --i) a[i]=a[i-1];
	for (int i=m; i; --i) b[i]=b[i-1];
	a[0]=b[0]=' ';
	pi();
	kmp();
}
int main()
{
	citire();
	afis();
	return 0;
}