Cod sursa(job #303906)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 10 aprilie 2009 14:49:20
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <cstdio>
#include <cstring>

using namespace std;

#define FIN "strmatch.in"
#define FOUT "strmatch.out"
#define Nmax 2001000
#define Nmin 1011

char a[Nmax];
char b[Nmax];
int pi[Nmax];
int sir[Nmin];
int n,m,nr;

inline void citire()
{
	int i,j;

	freopen(FIN,"r",stdin);
	freopen(FOUT,"w",stdout);

	scanf("%s\n", a+1);
	scanf("%s\n", b+1);

	n=strlen(a+1);
	m=strlen(b+1);
}

inline void prefix()
{
	int i,j,k;

	k=0;
	pi[1]=0;
	for (i=2;i<=n;++i)
	{
		while(k>0 && a[i]!=a[k+1])
			 k=pi[k];
		if (a[i]==a[k+1])
			 k++;
		pi[i]=k;
	}
}

inline void kmp()
{
	int i,j,k;

	k=0;
	nr=0;
	for (i=1;i<=m;++i)
	{
		while(k>0 && b[i]!=a[k+1])
			 k=pi[k];
		if (b[i]==a[k+1])
			k++;
		if (k==n)
		{
			nr++;
			if (sir[0]<1000)
			{
				sir[++sir[0]]=i-n;
			}
			else
			++sir[0];
		}
	}
}


inline void scrie()
{
	int i;
	prefix();
	kmp();
	printf("%d\n", nr);
	for (i=1;i<=sir[0] && i<=1000;++i)
		 printf("%d ", sir[i]);
}


int main()
{
	citire();
	scrie();

	fclose(stdin);
	fclose(stdout);

	return 0;
}