Cod sursa(job #600085)

Utilizator cosmyoPaunel Cosmin cosmyo Data 30 iunie 2011 16:02:33
Problema ADN Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.93 kb
#include <fstream>
#include <cstring>
using namespace std;
const int N = 30005;
const int M = 18;
int L[N], n, cost[M][M], d[M][1 << M], sol[M][1 << M];
char s[M][N];

inline void prefix(int j) {
    int i, n, k;
    n = strlen(s[j]);
    L[1] = 0;
    for(i = 2; i <= n; ++i) {
        while(k && s[j][k] != s[j][i - 1])
            k = L[k];
        if(s[j][k] == s[j][i - 1])
            ++k;
        L[i] = k;
    }
}

inline int kmp(int p, int t){
    int max = 0, i, k, n = strlen(s[t]), m = strlen(s[p]);
    k = 0;
    for(i = 1; i <= n; ++i){
        while(k && s[p][k] != s[t][i - 1])
            k = L[k];
        if(s[p][k] == s[t][i - 1])
            ++k;
        if(k == m){
            return k;
            k = L[k];
        }
    }

    return k;
}

int main() {
    ifstream fin("adn.in");
    ofstream fout("adn.out");
    int i, j, sw, k;
    fin >> n;
    --n;
    for(i = 0; i <= n; ++i)
        fin >> s[i];
    /*
    for(i = 0; i <= n; ++i){
        memset(L, 0, sizeof(L));
        prefix(i);
        sw = 0;
        for(j = 0; j <= n; ++j)
            if(i != j){
                  //fout << i + 1 << " " << j + 1 << " " << kmp(i, j) << '\n';
                if(kmp(i, j) == strlen(s[i])){
                        sw = 1;
                        break;
                }
            }
            if(sw){
                strcpy(s[i], s[j]);
                --n;
                --i;
            }
    }
    */
 //   fout << n << '\n';
    for(i = 0; i <= n; ++i){
        memset(L, 0, sizeof(L));
        prefix(i);
        for(j = 0; j <= n; ++j)
            if(i != j){
                cost[j][i] = kmp(i, j);
            }
    }
    //return 0;
    for(j = 1; j < (1 << (n + 1)); ++j)
        for(i = 0; i <= n; ++i)
            if((1 << i) & j)
                for(k = 0; k <= n; ++k)
                    if(((1 << k) & j) && i != k)
                        if(d[i][j] < d[k][j ^ (1 << i)] + cost[i][k]){
                            d[i][j] = d[k][j ^ (1 << i)] + cost[i][k];
                            sol[i][j] = k;
                        }
    int max = 0, p = -1;
  /*  for(i = 0; i <= n; ++i)
        fout << s[i] << '\n';
    for(i = 0; i <= n; ++i){
        for(j = 0; j <= n; ++j)
            fout << cost[i][j] << " ";
            fout << '\n';
    }
   */
  //  for(i = 0; i <= n; ++i)
  //      fout << i << " " <<  d[i][(1 << (n + 1)) - 1] << '\n';

    for(i = 0; i <= n; ++i)
        if(max < d[i][(1 << (n + 1)) - 1])
            max = d[i][(1 << (n + 1)) - 1], p = i;

    int solutie[M], nr = 0;
    j = (1 << (n + 1)) - 1;
        while(j) {
            solutie[++nr] = p;
            i = p;
            p = sol[p][j];
            j ^= 1 << i;
        }
        fout << s[solutie[1]];
        for(i = 2; i <= nr; ++i)
            fout << s[solutie[i]] + cost[solutie[i - 1]][solutie[i]];

        fout << '\n';

    return 0;
}