Cod sursa(job #303891)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 10 aprilie 2009 14:41:33
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <cstdio>
#include <cstring>

using namespace std;

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


char a[Nmax];
char b[Nmax];
int pi[Nmax];
int sir[Nmax];
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)
		 printf("%d ", sir[i]);
}


int main()
{
	citire();
	scrie();
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}