Cod sursa(job #1071266)

Utilizator dan_tudorDan Tudor dan_tudor Data 2 ianuarie 2014 20:36:28
Problema ADN Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.16 kb
#include<fstream>
#include<string.h>
#include<algorithm>

using namespace std;

#define infinit 0x3f3f3f3f
#define lg 20

int n, i, nr[lg], j, k, s, q, raspuns, d[lg][lg], a[lg][300000], urm[30005], gs, poz, pus[lg], nrs, sol[lg];
char fst[lg][300000], v[lg][30005];
const int pt[] = {0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144};

void prefix(int ct){
    int k = 0;

    for (int i = 2; i <= nr[ct]; i ++){
        while (k > 0 && v[ct][k+1] != v[ct][i])
            k = urm[k];

        if (v[ct][k+1] == v[ct][i])
            k ++;

        urm[i] = k;
    }
}
int main()
{    ifstream cin("adn.in");
     ofstream cout("adn.out");

 // citesc sirurile
    cin>>n;
    for (i = 1; i <= n; i ++){
      cin.getline(v[i]+1,30001);
        nr[i] = strlen(v[i]+1);
    }
//functia prefix (KMP) pentru sirul i
    for (i = 1; i <= n; i ++)
        if (!pus[i]){
            memset(urm, 0, sizeof(urm));
            prefix(i);

            for (k = 1; k <= n; k ++)
                if (!pus[k] && i != k){
                    s = 0, q = 0;

                    for (j = 1; j <= nr[k]; j ++){
                        while (q > 0 && v[i][q+1] != v[k][j])
                            q = urm[q];

                        if (v[i][q+1] == v[k][j])
                            q ++;
                        if (q == nr[i]){
                            s = 1;
                            break;
                        }
                        if (j == nr[k])
                            gs = q;
                    }

                    if (s){
                        pus[i] = 1;//l-am cuplat
                        d[k][i] = nr[i];
                    }
                    else
                        d[k][i] = gs;// cate se potrivesc

                }
        }

    for (i = 1; i <= n; i ++)
        if (pus[i])
            nrs |= pt[i];

    for (i = 1; i < (1 << n); i ++)
        for (j = 1; j <= n; j ++)
            a[j][i] = infinit;

    for (i = 1; i <= n; i ++)
        if (!pus[i])
            a[i][nrs | pt[i]] = nr[i];


    for (j = 1; j < (1 << n); j ++)
        for (i = 1; i <= n; i ++)
            if (!pus[i])
                if (a[i][j] != infinit)
                    for (k = 1; k <= n; k ++)
                        if (!(j & pt[k]) && !pus[k]){
                            int nxt = j | pt[k];

                            if (a[i][j] + nr[k] - d[i][k] < a[k][nxt]){
                                a[k][nxt] = a[i][j] + nr[k] - d[i][k];
                                fst[k][nxt] = i;
                            }
                        }

    raspuns = infinit;
    for (i = 1; i <= n; i ++)
        if (a[i][(1 << n) - 1] < raspuns && !pus[i]){
            raspuns = a[i][(1 << n) - 1];
            poz = i;
        }


    nrs = (1 << n) - 1;
    while (poz){
        sol[++sol[0]] = poz;

        int x = poz;
        poz = fst[poz][nrs];
        nrs ^= pt[x];
    }
    for (i = sol[0]; i; i --){

        for (j = d[sol[i+1]][sol[i]]+1; j <= nr[sol[i]]; j ++)
            cout<<v[sol[i]][j];
    }


    return 0;
}