Cod sursa(job #699294)

Utilizator arch_enemyAngela Gossow arch_enemy Data 29 februarie 2012 18:42:35
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <cstdio>
#include <cstring>

#define LMAX 2000005

char P[LMAX], S[LMAX];
int Pi[LMAX], Sol[LMAX], i, LgCt, LgP, LgS;

inline void Prefix()
{
	for( Pi[1] = LgCt = 0, i = 2; i <= LgP; ++i )
	{
		for( ; P[LgCt + 1] != P[i] && LgCt; LgCt = Pi[LgCt] );
		if( P[LgCt + 1] == P[i] ) ++LgCt;
		Pi[i] = LgCt;
	}
}

inline void KMP()
{
	Sol[0] = 0;
	for( LgCt = 0, i = 1; i <= LgS; ++i )
	{
		for( ; P[LgCt + 1] != S[i] && LgCt; LgCt = Pi[LgCt] );
		if( P[LgCt + 1] == S[i] ) ++LgCt;
		if( LgCt == LgP )
		{
			LgCt = Pi[LgP];
			if( Sol[0] < 1000 )
				Sol[ ++Sol[0] ] = i - LgP + 1;
			else break;
		}
	}
}

int main()
{
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	
	fgets( P + 1, LMAX, stdin );
	LgP = strlen( P + 1 ) - 1;
	fgets( S + 1, LMAX, stdin );
	LgS = strlen( S + 1 ) - 1;
	
	Prefix();
	KMP();
	
	printf("%d\n", Sol[0] );
	for( i = 1; i <= Sol[0]; ++i )
		printf("%d ", Sol[i] - 1 );
	printf("\n");
	
	return 0;
}