Cod sursa(job #2961836)

Utilizator andriciucandreeaAndriciuc Andreea andriciucandreea Data 7 ianuarie 2023 02:52:11
Problema ADN Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.9 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>

#define MAXN (1 << 18)
#define oo 0x3f3f3f3f

using namespace std;

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

int n, minim = oo, poz;
vector<string> text;
int pi[30005];
int C[MAXN + 5][20], Cost[20][20];

void compute(string cuv)
{
    int q = 0;
    pi[1] = 0;
    for (int i = 2; i <= cuv.length(); i++)
    {
        while (q && cuv[q] != cuv[i - 1])
            q = pi[q];
        if (cuv[q] == cuv[i - 1])
            q++;
        pi[i] = q;
    }
}

int KMP(string cuv1, string cuv2)
{
    int q = 0;
    for (int i = 1; i <= cuv2.length(); i++)
    {
        while (q && cuv1[q] != cuv2[i - 1])
            q = pi[q];
        if (cuv1[q] == cuv2[i - 1])
            ++q;
        if (q == cuv1.length() - 1)
            return 0;
    }
    return cuv1.length() - q;
}

void reconstruct(int mask, int varf)
{
    if ((mask & (mask - 1)) == 0)
    {
        for (int i = 0; i < n; ++i)
            if ((1 << i) == mask)
            {
                fout << text[i];
                return;
            }
    }
    int mask2 = mask ^ (1 << varf);
    for (int i = 0; i < n; ++i)
    {
        if (C[mask][varf] == C[mask2][i] + Cost[i][varf])
        {
            reconstruct(mask2, i);
            fout << text[varf].substr(text[varf].length() - Cost[i][varf]);
            return;
        }
    }
}

void lant()
{
    for (int mask = 1; mask < (1 << n); ++mask)
        for (int pos = 0; pos < n; ++pos)
            if (mask & (1 << pos))
            {
                int mask2 = mask ^ (1 << pos);
                if (mask2 == 0)
                {
                    C[mask][pos] = text[pos].length();
                    break;
                }
                for (int j = 0; j < n; ++j)
                    if (mask2 & (1 << j))
                        C[mask][pos] = min(C[mask][pos], C[mask2][j] + Cost[j][pos]);
            }
    for (int i = 0; i < n; ++i)
        if (C[(1 << n) - 1][i] < minim)
            minim = C[(1 << n) - 1][i], poz = i;
    reconstruct((1 << n) - 1, poz);
}


int main()
{
    fin >> n;
    string s;
    for (int i = 0; i < n; i++)
        fin >> s, text.push_back(s);
    memset(C, oo, sizeof(C));
    bool gasit = false;
    do {
        gasit = false;
        for (int i = 0; i < n; ++i)
        {
            compute(text[i]);
            for (int j = 0; j < n; ++j)
                if (i != j && !(KMP(text[i], text[j])))
                {
                    n--;
                    gasit = true;
                    text.erase(text.begin() + i);
                }
        }
    } while (gasit);
    for (int i = 0; i < n; i++)
    {
        compute(text[i]);
        for (int j = 0; j < n; j++)
            if (i != j)
                Cost[j][i] = KMP(text[i], text[j]);
    }
    lant();
    return 0;
}