Cod sursa(job #195396)

Utilizator webspiderDumitru Bogdan webspider Data 18 iunie 2008 11:59:32
Problema ADN Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.65 kb
#include <stdio.h>
#include <iostream>

using namespace std;

const int maxN = 21;
const int maxC = 32002;
const int maxCD = 300000;
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;
            }
        if ( lC >= maxCD ) return 0;
	}
	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;
}