Pagini recente » Cod sursa (job #2116176) | Cod sursa (job #164366) | Cod sursa (job #2955028) | Cod sursa (job #446916) | Cod sursa (job #195397)
Cod sursa(job #195397)
#include <stdio.h>
#include <iostream>
using namespace std;
const int maxN = 21;
const int maxC = 32002;
const int maxCD = 1000000;
const int modH = 666013;
const int bzH = 19;
int N;
int sol;
int parent[ maxCD ];
char str[ maxN ][ maxC ];
char tmp[ maxN ][ maxC ];
int ln[ maxN ];
int solOrd[ maxN ];
int supp[ maxN ][ maxN ];
int coada[ maxCD ][ 3 ];
int lC;
long long hash1, hash2;
long long powF( int bz, int exp ) {
long long rez = 1;
long long aux = bz;
for ( int i = 0; i < 16; i++ ) {
if ( exp & ( 1 << i ) )
rez = ( rez * aux ) % modH;
aux = ( aux * aux ) % modH;
}
return rez;
}
int main()
{
#ifndef PC_COMPILE
freopen("adn.in","r",stdin);
freopen("adn.out","w",stdout);
#endif
#ifdef PC_COMPILE
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
#endif
scanf("%d\n", &N );
for ( int i = 0; i < N; i++ ) {
scanf("%s\n", tmp[ i ] );
ln[i] = strlen( tmp[i] );
}
int M =0;
for ( int i = 0; i < N; i++ ) {
hash1 = 0;
for ( int j = 0; j < ln[i]; j++ )
hash1 = ( hash1 + tmp[i][j]*powF( bzH, ln[i]-(j+1) ) ) % modH;
int ins = 1;
for ( int j = 0 && ins; j < N; j++ )
if ( ln[i] <= ln[j] && i != j) {
hash2 = 0;
for ( int k = 0; k < ln[i]; k++ )
hash2 = ( hash2 + tmp[j][k]*powF( bzH, ln[i]-(k+1) ) ) % modH;
if ( hash1 == hash2 ) {
ins = 0;
break;
}
for ( int k = ln[i]; k < ln[j]; k++ ) {
hash2 = ( hash2 + 100*modH - tmp[j][k-ln[i]]*powF( bzH, ln[i]-1 ) ) % modH;
hash2 = ( hash2 * bzH + tmp[j][k] ) % modH;
if ( hash2 == hash1 ) {
ins = 0;
break;
}
}
}
if ( ins ) {
memcpy( str[M], tmp[i], sizeof( tmp[i] ) );
M++;
}
}
memset( ln, 0, sizeof( ln ) );
N = M;
for ( int i = 0; i < N; i++ ) {
ln[ i ] = strlen( str[i] );
supp[ N ][ i ] = 1;
}
for ( int i = 0; i < N; i++ )
for ( int j = 0; j < N; j++ ) {
hash1 = 0, hash2 = 0;
for ( int l = 1; l <= min( ln[i], ln[j] ); l++ ) {
hash1 = ( hash1 + str[i][ ln[i] - l ]*powF( bzH, l-1 ) ) % modH;
hash2 = ( hash2*bzH + str[j][ l-1 ] ) % modH;
if ( hash1 == hash2 )
supp[i][j] = l;
}
}
coada[ lC ][ 0 ] = 0;
coada[ lC ][ 1 ] = N;
coada[ lC ][ 2 ] = 1;
for ( int i = 0; i <= lC; i++ ) {
//printf("[ %d ][ %d %d %d ]( %d )\n", i, coada[i][0], coada[i][1], coada[i][2], parent[i] );
if ( coada[i][0] == ( 1 << N ) - 1 ) {
if ( !sol || coada[i][2] < coada[sol][2] )
sol = i;
}
for ( int j = 0; j < N; j++ )
if ( ! ( coada[i][0] & ( 1 << j ) ) ) {
lC++;
coada[ lC ][ 0 ] = coada[i][0] + ( 1 << j );
coada[ lC ][ 1 ] = j;
coada[ lC ][ 2 ] = coada[i][2] + ln[j] - supp[ coada[i][1] ][ j ];
parent[ lC ] = i;
}
}
int i = N-1;
while ( sol ) {
solOrd[ i ] = coada[ sol ][ 1 ];
sol = parent[sol];
i--;
}
solOrd[N] = N+1;
for ( int i = 0; i < N; i++ ) {
for ( int j = 0; j < ln[ solOrd[i] ] - supp[ solOrd[i] ][ solOrd[i+1] ]; j++ )
printf("%c", str[ solOrd[i] ][ j ] );
}
printf("\n");
return 0;
}