Cod sursa(job #1538462)

Utilizator algebristulFilip Berila algebristul Data 29 noiembrie 2015 02:19:41
Problema ADN Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.45 kb
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <fstream>

#define FILEIN "adn.in"
#define FILEOUT "adn.out"

using namespace std;

const int INF  = 0x3f3f3f3f;
const int NMAX = 18;
const int LMAX = 30011;

int S[NMAX][NMAX];
char A[NMAX][LMAX];
int D[1<<NMAX][NMAX];
int T[1<<NMAX][NMAX];
int n;
vector<int> Sol;

void prefix(char x[], int p[]) {
    int X = strlen(x);

    p[0] = -1;

    int k = -1;
    for (int i = 1; i < X; i++) {
        while (k != -1 && x[k + 1] != x[i])
            k = p[k];

        if (x[k + 1] == x[i])
            k++;

        p[i] = k;
    }
}

int kmp(char x[], char y[]) {
    int p[LMAX];

    prefix(x, p);

    int X = strlen(x);
    int Y = strlen(y);

    int k = -1;
    for (int i = 0; i < Y; i++) {
        while (k != -1 && x[k + 1] != y[i])
            k = p[k];

        if (x[k + 1] == y[i])
            k++;

        if (k == X - 1)
            break;
    }

    return X - 1 - k;
}

void hamilton() {
    memset(D, INF, sizeof(D));

    for (int i = 0; i < n; i++)
        D[(1 << i)][i] = strlen(A[i]);

    for (int i = 1; i < (1 << n); i++) {
        for (int k = 0; k < n; k++) {
            if (i & (1 << k)) {
                for (int l = 0; l < n; l++) {
                    if (i & (1 << l))
                        continue;

                    if (D[i | (1 << l)][l] > D[i][k] + S[k][l]) {
                        D[i | (1 << l)][l] = D[i][k] + S[k][l];
                        T[i | (1 << l)][l] = k;
                    }
                }
            }
        }
    }

    int min = INF, idx = -1;
    for (int k = 0; k < n; k++) {
        if (D[(1 << n) - 1][k] < min) {
            min = D[(1 << n) - 1][k];
            idx = k;
        }
    }

    int tmp = (1 << n) - 1;
    while (tmp != 0) {
        Sol.push_back(idx);
        int aux = idx;
        idx = T[tmp][idx];
        tmp -= (1 << aux);
    }

    reverse(Sol.begin(), Sol.end());
}

int main() {
    freopen(FILEIN, "r", stdin);
    freopen(FILEOUT, "w", stdout);
    cin.sync_with_stdio(0);

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j)
                continue;
            S[i][j] = kmp(A[j], A[i]);
        }
    }

    hamilton();

    cout << A[Sol[0]];
    for (int i = 1; i < Sol.size(); i++) {
        cout << A[Sol[i]] + strlen(A[Sol[i]]) - S[Sol[i-1]][Sol[i]];
    }
    cout << '\n';

    return 0;
}