Cod sursa(job #1321303)

Utilizator retrogradLucian Bicsi retrograd Data 18 ianuarie 2015 23:16:05
Problema ADN Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include<fstream>
#include<vector>
#include<cstring>

#define MAXC 30002
#define MAXN 20

using namespace std;

ifstream fin("adn.in");
ofstream fout("adn.out");

int PI[MAXC];
char CUVANT[MAXN][MAXC];
int n;
int G[MAXN][MAXN];

int alg(char *C1, char *C2) {
    int i;
    PI[1] = 0;
    PI[0] = -1;
    for(i=1; C2[i]; i++) {
        int j=PI[i-1];
        while(j!=-1 && C2[i]!=C1[j+1]) {
            j = PI[j];
        }

        PI[i] = j + 1;
    }
    return PI[i-1];
}

int ssol, bestsol = -1;

bool TAKEN[MAXN];
int SOL[MAXN], BEST[MAXN];

void checksol() {
    if(ssol > bestsol) {
        bestsol = ssol;
        for(int i=1; i<=n; i++) {
            BEST[i] = SOL[i];
        }
    }
}

void hamilton(int nod, int pas) {
    TAKEN[nod] = 1;
    SOL[pas] = nod;
    if(pas == n) {
        checksol();
    } else {
    for(int i = 1; i<=n; i++) {
        if(!TAKEN[i]) {
            ssol += G[nod][i];
            hamilton(i, pas+1);
            ssol -= G[nod][i];
        }
    }
    }
    TAKEN[nod] = 0;
}

void citire() {
    fin>>n;
    for(int i=1; i<=n; i++) {
        fin>>(CUVANT[i]+1);
        CUVANT[i][0] = '#';
    }
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            if(j == i) continue;
            if(strstr(CUVANT[i]+1, CUVANT[j]+1)) {
            G[i][j] = 0;
            CUVANT[j][0] = 0;
            } else {
            G[i][j] = alg(CUVANT[i], CUVANT[j]);
            }
        }
    }
}

void solve() {
    for(int i=1; i<=n; i++) {
        hamilton(i, 1);
    }
}

int main() {
    citire();
    solve();
    for(int i=n; i>=1; i--) {
        for(int j=1; j<strlen(CUVANT[BEST[i]]) - G[BEST[i-1]][BEST[i]]; j++) {
            fout<<(char)CUVANT[BEST[i]][j];
        }
    }

    return 0;
}