Cod sursa(job #230397)

Utilizator alexeiIacob Radu alexei Data 13 decembrie 2008 20:27:21
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include<stdio.h>
#include<string.h>
#define NMAX 2000005
#define NMIN 1024

char A1[NMAX],A2[NMAX];
int last[NMAX],sol[NMIN];
int N,M;
long long ANS;

void solve_1()
{
	int i,curr=0;
	for(i=2; i<=N; ++i)
	{
		while( curr && A1[i]!=A1[curr+1] ) curr=last[curr];
		if( A1[i]==A1[curr+1] ) ++curr;
		last[i]=curr;
	}
}

void solve_2()
{
	int i,curr=0;
	for(i=1; i<=M; ++i)
	{
		while( curr && A2[i]!=A1[curr+1] ) curr=last[curr];
		if( A2[i]==A1[curr+1] ) ++curr;
		if( curr==N )
		{
			++ANS;
			if( ANS<=1000 )
				sol[++sol[0]]=i-curr;
			curr=last[curr];
		}
	}
}

void show()
{
	int i;
	printf("%lld\n",ANS);
	for(i=1; i<=sol[0]; ++i)
		printf("%d ",sol[i]);
	printf("\n");
}

int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);

	scanf("%s",A1+1);
	scanf("%s",A2+1);

	N=strlen(A1+1);
	M=strlen(A2+1);
	
	solve_1();
	solve_2();
	show();

	return 0;
}