Pagini recente » Cod sursa (job #747729) | Cod sursa (job #2113338) | Cod sursa (job #2894426) | Cod sursa (job #742212) | Cod sursa (job #165869)
Cod sursa(job #165869)
// ADN - infoarena (KMP + ciclu hamiltonian de cost minim)
#include <stdio.h>
#include <string.h>
#define NX 19
#define LX 30010
#define INF 666666
int N, M, res;
int pi[ NX ][ LX ], a[ NX ][ NX ], b[ NX ][ NX ];
int L[ NX ], del[ NX ], map[ NX ], sol[ NX ], st[ NX ], V[ NX ];
char cuv[ NX ][ LX ];
void calc_pi( int x ) {
int i, k;
for( pi[x][0] = k = -1, i = 1; i <= L[x]; pi[x][i++] = ++k )
while( cuv[x][i] != cuv[x][k+1] && k>=0 )
k = pi[x][k];
}
void cit() {
int i;
scanf( "%d ", &N );
for( i = 1; i <= N; i++ ) {
cuv[i][0] = ' ';
gets( cuv[ i ] + 1 );
L[i] = strlen( cuv[i] + 1 );
calc_pi( i );
}
}
int match( int x, int y ) {
int i, k;
for( i = 1, k = 0; i <= L[x]; i++ ) {
while( cuv[x][i] != cuv[y][k+1] && k >= 0 )
k = pi[y][k];
if( ++k == L[y] )
break;
}
return L[y] - k;
}
void normalize() {
int i, j, Min, pMin;
for( i = 1; i <= N; i++ ) {
Min = INF, pMin = 0;
for( j = 1; j <= N; j++ )
if( i != j ) {
a[i][j] = match( i, j );
if( Min > a[i][j] )
Min = a[i][j], pMin = j;
}
if( Min <= 0 )
del[ pMin ] = 1;
}
for( i = 1, M = 0; i <= N; i++ )
if( del[i] == 0 )
map[ ++M ] = i;
for( i = 1; i <= M; i++ )
for( j = 1; j <= M; j++ )
b[i][j] = a[ map[i] ][ map[j] ];
}
int check() {
int i, s;
for( s = 0, i = 1; i < M; i++ )
s += b[ st[i] ][ st[i+1] ];
if( res > s ) {
res = s;
memcpy( sol, st, sizeof( st ) );
}
return 0;
}
int baga( int k ) {
int i;
if( k > M ) {
check();
return 0;
}
for( i = 1; i <= M; i++ )
if( V[i] == 0 && (b[ st[k-1] ][ i ] != 0 || k == 1) ) {
V[i] = 1; st[k] = i;
baga( k+1 );
V[i] = 0;
}
return 0;
}
void rez() {
normalize();
res = INF;
baga( 1 );
}
void scr() {
int i, j;
/*
for( i = 1; i <= N; i++ ) {
for( j = 1; j <= L[i]; j++ )
printf( "%d ", pi[i][j] );
printf( "\n" );
}
printf( "\n" );
for( i = 1; i <= N; i++ ) {
for( j = 1; j <= N; j++ )
printf( "%d ", a[i][j] );
printf( "\n" );
}
printf( "\n" );
for( i = 1; i <= M; i++ )
printf( "%d ", map[i] );
printf("\n" );
printf( "%d\n", L[ map[1] ] + res );
for( i = 1; i <= M; i++ )
printf( "%d ", map[ sol[i] ] );
*/
fputs( cuv[ map[ sol[1] ] ] + 1, stdout );
for( i = 2; i <= M; i++ )
fputs( cuv[ map[ sol[i] ] ] + L[ map[sol[i]] ] - b[ sol[i-1] ][ sol[i] ] + 1, stdout );
printf( "\n" );
}
int main() {
freopen( "adn.in", "r", stdin );
freopen( "adn.out", "w", stdout );
cit();
rez();
scr();
return 0;
}