Cod sursa(job #1014969)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 23 octombrie 2013 18:53:24
Problema ADN Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.68 kb
#include<stdio.h>
#include<string.h>

#define NMAX 300007
#define MMAX (1 << 19)
#define LMAX 20
#define INF 1000000

int Pi[LMAX][LMAX], D[MMAX][LMAX], Pred[MMAX][LMAX], Lung[LMAX], C[LMAX][LMAX];
char a[LMAX][NMAX];
int B, n;

void prefix(char a[NMAX], int pi[NMAX], int n){
    int x = 0;
    pi[1] = 0;
    for(int i = 2; i <= n; ++ i){
        while(x > 0 && a[x + 1] != a[i])
            x = pi[x];
        if(a[x + 1] == a[i])
            ++ x;
        pi[i] = x;
    }
}

inline int KMP(int Indi, int Indj){
    int x = 0;
    for(int i = 1; i <= Lung[Indi]; ++ i){
        while(x > 0 && a[Indi][i] != a[Indj][x + 1])
            x = Pi[Indj][x];
        if(a[Indi][i] == a[Indj][x + 1])
            ++ x;
        if(x == Lung[Indj]){
            B |= (1 << Indj);
            return x;
        }
    }
    return x;
}

void dinamic(){
    for(int i = 1; i < (1 << n); ++ i)
        for(int j = 0; j < n; ++ j){
            D[i][j] = INF;
            Pred[i][j] = -1;
        }
    for(int i = 0; i < n; ++ i)
        D[(1 << i)][i] = Lung[i];
    for(int i = 1; i < (1 << n); ++ i)
        for(int j = 0; j < n; ++ j)
            if(i & (1 << j))
                for(int k = 0; k < n; ++ k)
                    if(k != j && (i & (1 << k))){
                        int Val = D[i ^ (1 << j)][k] - C[k][j] + Lung[j];
                        if(D[i][j] > Val){
                            D[i][j] = Val;
                            Pred[i][j] = k;
                        }
                    }
}

void afisare(int D[NMAX][LMAX]){
    for(int i = 1; i < (1 << n); ++ i, printf("\n"))
        for(int j = 0; j < n; ++ j)
            printf("%d ", D[i][j]);
}

void afis(int x, int y) {
    ///printf("%d %d\n", x, y);
    int Val = x - (1 << y);
    if(Pred[x][y] == -1) {
        printf("%s",a[y] + 1);
        return;
    }
    afis(Val, Pred[x][y]);
    for(int i = C[Pred[x][y]][y] + 1;i <= Lung[y]; ++ i)
        printf("%c", a[y][i]);
}

int main(){
    freopen("adn.in", "r", stdin);
    freopen("adn.out", "w", stdout);
    scanf("%d\n", &n);
    for(int i = 0; i < n; ++ i){
        gets(a[i] + 1);
        Lung[i] = strlen(a[i] + 1);
        prefix(a[i], Pi[i], Lung[i]);
    }
    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < n; ++ j)
            if(i != j)
                C[i][j] = KMP(i, j);
    dinamic();
    ///afisare(C);
    ///afisare(D);
    ///afisare(Pred);
    int Ans = INF, Poz = 0;
    for(int i = 0; i < n; ++ i){
        int Val = D[((1 << n) - 1) ^ B][i];
        if(Val < Ans){
            Ans = Val;
            Poz = i;
        }
    }
    afis(((1 << n) - 1) ^ B, Poz);
    return 0;
}