Cod sursa(job #475028)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 5 august 2010 18:50:23
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <cstdio>
#include <cstring>

#define file_in "strmatch.in"
#define file_out "strmatch.out"

#define nmax 2010000

int n,m;
char a[nmax];
char b[nmax];
int sir[nmax];
int pi[nmax];

void citire()
{
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	gets(a+1);
	n=strlen(a+1);
	gets(b+1);
	m=strlen(b+1);
}

void solve()
{
	int i,k;
	//baga prefix
	k=0;
	pi[1]=0;
	for (i=2;i<=n;++i)
	{
		while(a[k+1]!=a[i] && k>0) k=pi[k];
		if (a[k+1]==a[i]) k++;
		pi[i]=k;
	}
	//baga kmp
	k=0;
	for (i=1;i<=m;++i)
	{
		while(a[k+1]!=b[i] && k>0) k=pi[k];
		if (a[k+1]==b[i]) k++;
		if (k==n)
		    sir[++sir[0]]=i-n;
	}
	
	printf("%d\n", sir[0]);
	for (i=1;i<=sir[0] && i<=1000;++i) printf("%d ", sir[i]);
}

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