Cod sursa(job #2155211)

Utilizator cosceexcosceex cosceex Data 7 martie 2018 18:09:20
Problema ADN Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.45 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>

using namespace std;

int N;
int automaton[30005];

const int oo = 2e9;
int d[262150][20];
int prv[262150][20];

string S[20];
string ans;
int cost[20][20];
vector <string> S2;

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

void afis(int sz)
{
    for(int i = 0; i < sz; ++i)
        cout<<automaton[i]<<" ";
    cout<<"\n";
}
void afis2(int conf, int x)
{
    //cout<<conf<<", "<<x<<"\n";
    if (conf == (1<<x))
    {
        ans+=S2[x];
        //cout<<"SIR CONSTRUIT MOMENTAN CU "<<x<<" ("<<ans<<") "<<"\n";
    }
    else
    {
        afis2(conf ^ (1 << x), prv[conf][x]);
        for(int i = cost[x][prv[conf][x]]; i < S2[x].size(); ++i)
            ans+=S2[x][i];
        //cout<<"SIR CONSTRUIT MOMENTAN CU "<<x<<" ("<<ans<<") "<<"\n";
    }
}
void kmp_fail(string s)
{
    memset(automaton, 0, sizeof(automaton));   //resetam automatul finit
    automaton[0] = 0;
    int j = 0;
    for (int i = 1; i < s.size(); ++i)
        {
        while(s[i] != s[j] && j > 0)
            j = automaton[j - 1];
        if(s[i] == s[j])
            ++j;
        automaton[i] = j;
        }
}

vector <string> prune ()    //caut pe i in j
{
    vector<string> ret;
    for(int i = 0; i < N; ++i)
    {
        kmp_fail(S[i]); //generam automatul pentru sirul S[i]
        bool gasit = false;
        for(int j = 0; j < N; ++j)
        {
            if(i == j) continue;
            //cout<<"Caut sirul \""<<S[i]<<"\" in sirul \""<<S[j]<<"\n";
            //cout<<"Automatul pt sirul cautat este: "; afis(S[i].size());
            int m = 0;
            int k = 0;
            while(k + m < S[j].size())
            {
                if(S[i][k] == S[j][k + m])
                {
                    if(k == S[i].size() - 1)
                    {
                        gasit = 1;
                        break;
                    }
                    ++k;
                }
                else
                {
                    if(k>0)
                    {
                        m += k - automaton[k - 1];
                        k = automaton[k - 1];
                    }
                    else
                        ++m;
                }
            }
            if(gasit)
                break;
        }
        if(!gasit)
            ret.push_back(S[i]);
    }
    return ret;
}

int potrivire(string a, string b)
{
    kmp_fail(a);
    int m = 0;
    int k = 0;
    while(k + m < b.size())
    {
        if(a[k] == b[k + m])
                ++k;
        else
            {
                if(k>0)
                    {
                        m += k - automaton[k - 1];
                        k = automaton[k - 1];
                    }
                else
                    ++m;
            }
    }
    return k;
}

int main()
{

    in>>N;
    for(int i = 0; i < N; ++i)
        in>>S[i];

    S2 = prune();
    N = S2.size();
    for(int i = 0; i < N; ++i)
        for(int j = 0; j < N; ++j)
        {
            if(i == j)
                continue;
            cost[i][j] = potrivire(S2[i], S2[j]); //j - i
            //cout<<"Sirul "<<j<<" ("<<S2[j]<<") se potriveste "<<cost[i][j]<<" caractere peste sirul "<<i<<" ("<<S2[i]<<")\n";
        }
    /*cout<<"\nSirurile care nu sunt continute sunt: \n";
    for(int i = 0; i < N; ++i)
        cout<<S2[i]<<"\n";*/

    //urmeaza dinamica
    for(int i = 0; i < (1<<N); ++i)
        for(int j = 0; j < N; ++j)
            d[i][j] = oo;
    for(int i = 0; i < N; ++i)
        d[(1<<i)][i] = S2[i].size();
    //cout<<"INIT OK!\n";
    for(int i = 0; i < (1<<N); ++i)
        for(int j = 0; j < N; ++j)
        {
            if(!(i & (1<<j)) || i == (1<<j))
                continue;
            for(int k = 0; k < N; ++k)
            {
                if(!(i & (1<<k)) || j == k)
                    continue;
                if(d[i][j] > d[i ^ (1<<j)][k] + S2[j].size() - cost[j][k])
                {
                    d[i][j] = d[i ^ (1<<j)][k] + S2[j].size() - cost[j][k];
                    prv[i][j] = k;
                }
            }

        }
    //cout<<"DINAMICA OK!\n";
    int best = 0;
    int i = ((1 << N) - 1);
    for (int j = 0; j < N; ++j)
        if (d[i][j] < d[i][best])
            best = j;
    //cout<<best<<"\n";
    afis2(i, best);
    out<<ans;
}