Cod sursa(job #291466)

Utilizator moonbeamElma Moonbeam moonbeam Data 29 martie 2009 21:22:54
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include<stdio.h>
#include<string.h>
#define Q 2000005
char A[Q],B[Q];
int k,n,m,v[1005],num,pi[Q];
void p()
{
	pi[1]=0;
	k=0;
	for (int i=2; i<=n; ++i)
	{
		while (k&&A[k+1]!=A[i])
			k=pi[k];
		if (A[k+1]==A[i])
			++k;
		pi[i]=k;
	}
}

void kmp()
{   
	k=0;
	for (int i=1; i<=m; ++i)
	{
		while (k&&A[k+1]!=B[i])
			k=pi[k];
		if (A[k+1]==B[i])
			++k;
		if (k==n)
		{
			++num;
			if (num<=1000)
				v[num]=i-n;
			k=pi[n];
		}
	}
}
void citire()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	fgets(A,sizeof(A),stdin);
	fgets(B,sizeof(B),stdin);
	for (; A[n]; ++n);--n;
	for (;B[m]; ++m);--m;
	for (int i=n; i; --i) A[i]=A[i-1];
	A[0]=' ';
	for (int i=m; i; --i) B[i]=B[i-1];
	B[0]=' ';
	p();
	kmp();
	printf("%d\n",num);
	for (int i=1; i<=num && i<=1000; ++i)
		printf("%d ",v[i]);
}
int main()
{
	citire();
	return 0;
}