Cod sursa(job #791768)

Utilizator SchumiDumitru Andrei Georgian Schumi Data 25 septembrie 2012 12:20:56
Problema ADN Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.38 kb
#include <cassert>
#include <cstdio>
#include <cstring>

using namespace std;


const int N = 19;
const int M = 30005;
const int INF = 0x3f3f3f3f;

int n, s;
int pi[N], len[N];
int d[1 << N][N], reconst[1 << N][N];
int shorter[N][N];
char sol[N * M];
char text[N][M];

void read() {
    assert(freopen("adn.in", "r", stdin) != NULL);
    assert(freopen("adn.out", "w", stdout) != NULL);

    assert(scanf("%d", &n) == 1);
    for (int i = 0; i < n; ++i) {
        assert(scanf(" %s ", text[i] + 1) == 1);
        len[i] = strlen(text[i] + 1);
    }
}

void prefix(char pattern[]) {
    memset(pi, 0, sizeof(pi));
    int p = 0;
    int n = strlen(pattern + 1);

    for (int i = 2; i <= n; ++i) {
        while (p > 0 && pattern[p + 1] != pattern[i])
            p = pi[p];

        if (pattern[p + 1] == pattern[i])
            ++p;

        pi[i] = p;
    }
}

int match(char pattern[], char text[]) {
    int p = 0;
    int n = strlen(text + 1);
    int m = strlen(pattern + 1);
    
    for (int i = 1; i <= n; ++i) {
        while (p > 0 && pattern[p + 1] != text[i])
            p = pi[p];

        if (pattern[p + 1] == text[i])
            ++p;

        if (p == m)
            return -1;
    }

    return p;
}

void preprocesare_kmp() {
    for (int i = 0; i < n; ++i) {
        prefix(text[i]);
        for (int j = 0; j < n; ++j) {
            if (i == j)
                continue;
            
            int x = match(text[i], text[j]);
            if (x == -1) {
                memcpy(text[i], text[n - 1], sizeof(text[n - 1]));
                len[i] = len[n - 1];
                --i; 
                --n;
                break;
            }
        }
    }
   
     /*for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) {
            if (i == j)
                continue;
            
            prefix(text[j]);
            shorter[i][j] = match(text[i], text[j]);
        }*/
}

void intializare() {
    for (int i = 0; i < (1 << n); ++i)
        for (int j = 0; j <= n; ++j)
            d[i][j] = INF;

    for (int i = 0; i < n; ++i)
        d[1 << i][i] = len[i];
}

void dinamica() {
    intializare();
    
    for (int conf = 1; conf < (1 << n); ++conf)
        for (int last = 0; last < n; ++last) {
            for (int newLast = 0; newLast < n; ++newLast) {
                if (last == newLast || (conf & (1 << newLast)))
                    continue;
                if (d[conf][last] + len[newLast] - shorter[last][newLast] < d[conf | (1 << newLast)][newLast]) {
                    d[conf | (1 << newLast)][newLast] = d[conf][last] + len[newLast] - shorter[last][newLast];
                    reconst[conf | (1 << newLast)][newLast] = last;
                }
            }
        }
}

void reconstituire() {
    int last = 0;

    for (int i = 0; i < n; ++i)
        if (d[1 << n][i] < d[1 << n][last])
            last = i;

    int conf = (1 << n) - 1;
    while (conf) {
        int newLast = reconst[conf][last];
        for (int i = len[last]; i > shorter[newLast][last]; --i)
            sol[++s] = text[last][i];

        conf &= ~(1 << last);
        last = newLast;
    }
}

void write() {
    for (int i = s; i > 0; --i)
        printf("%c", sol[i]);
}

int main() {
    read();
    preprocesare_kmp();
    //fprintf(stderr, "%d", n);
    //for (int i = 0; i < 4; ++i) {
      //      printf("%s ", text[i] + 1);
        //printf("\n");
    //}
    dinamica();
    reconstituire();
    write();
}