Cod sursa(job #1200842)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 23 iunie 2014 18:00:18
Problema ADN Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.94 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>

using namespace std;

const int Nmax = 18;
const int Lmax = 1e5 + 2;
const int inf = 0x3f3f3f3f;

char S[Nmax][Lmax];
int C[Nmax][Nmax];
int D[1 << Nmax][Nmax];
int pi[Lmax];
int N;

void build_prefix( char s[] )
{
    int lgprefix = 0;
    int n = strlen( s + 1 );

    pi[1] = 0;

    for ( int i = 2; i <= n; ++i )
    {
        while ( lgprefix && s[i] != s[lgprefix + 1] )
                lgprefix = pi[lgprefix];

        if ( s[i] == s[lgprefix + 1] )
                lgprefix++;

        pi[i] = lgprefix;
    }
}

int KMP_cost( char patt[], char text[] )
{
    int n = strlen( patt + 1 );
    int m = strlen( text + 1 );

    int lgprefix = 0;

    for ( int i = 1; i <= m; ++i )
    {
        while ( lgprefix && text[i] != patt[lgprefix + 1] )
                lgprefix = pi[lgprefix];

        if ( text[i] == patt[lgprefix + 1] )
                lgprefix++;

        if ( lgprefix == n )
                return n;
    }

    return lgprefix;
}

int cycle( int stare, int nodAnterior )
{
    if ( D[stare][nodAnterior] != -1 )
            return D[stare][nodAnterior];

    if ( stare == ( 1 << N ) - 1 )
    {
        return 0;
    }
    else
    {
        D[stare][nodAnterior] = -inf;

        for ( int i = 0; i < N; ++i )
        {
            if ( ( stare & ( 1 << i ) ) == 0 )
            {
                int ans = C[nodAnterior][i] + cycle( stare ^ ( 1 << i ), i );

                if ( ans > D[stare][nodAnterior] )
                {
                    D[stare][nodAnterior] = ans;
                }
            }
        }

        return D[stare][nodAnterior];
    }
}

int sol[Nmax];
int P[Nmax];

void perm()
{
    for ( int i = 0; i < N; ++i )
            P[i] = i;

    int maxim = 0;

    do
    {
        int sum = 0;

        for ( int i = 0; i < N - 1; ++i )
                sum += C[ P[i] ][ P[i + 1] ];

        if ( sum > maxim )
        {
            for ( int i = 0; i < N; ++i )
                    sol[i] = P[i];

            maxim = sum;
        }

    } while ( next_permutation( P, P + N ) );

    int sum = 0;

    for ( int i = 0; i < N; ++i )
            sum += strlen( S[i] + 1 );

    //cout << sum - maxim << endl;
}

int main()
{
    ifstream cin("adn.in");
    ofstream cout("adn.out");

    cin >> N;

        for ( int i = 0; i < N; ++i )
        {
            cin >> ( S[i] + 1 );
        }

        // for ( int i = 0; i < N; ++i )
            //    cout << ( S[i] + 1 ) << " " << strlen( S[i] + 1 ) << endl;

        //  cout << endl;

        for ( int i = 0; i < N; ++i )
        {
            build_prefix( S[i] );

            for ( int j = 0; j < N; ++j )
                    if ( i != j )
                        C[j][i] = KMP_cost( S[i], S[j] );
        }

        for ( int i = 0; i < N; ++i )
                for ( int j = 0; j < N; ++j )
                    if ( i != j )
                        if ( C[i][j] == strlen( S[j] + 1 ) )
                                C[j][i] = strlen( S[j] + 1 );

        // for ( int i = 0; i < ( 1 << N ); ++i )
         //       for ( int j = 0; j < N; ++j )
           //         D[i][j] = -1;

        // for ( int i = 0; i < N; ++i, cout << endl )
            //    for ( int j = 0; j < N; ++j )
               //         cout << C[i][j] << " ";

        /**for ( int i = 0; i < N; ++i )
        {
            cout << cycle( 1 << i, i ) << "\n";
        }

        cout << endl;
        **/
        perm();

         for ( int i = 0; i < N - 1; ++i )
        {
            int cat = strlen( S[ sol[i] ] + 1 ) - C[ sol[i] ][ sol[i + 1] ];

            for ( int j = 1; j <= cat; ++j )
                    cout << S[ sol[i] ][j];
        }

        for ( int j = 1; j <= strlen( S[ sol[N - 1] ] + 1 ); ++j )
                cout << S[ sol[N - 1] ][j];

    return 0;
}