Cod sursa(job #2136301)

Utilizator Y0da1NUME JMECHER Y0da1 Data 19 februarie 2018 20:19:53
Problema ADN Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.23 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, -1, sizeof(automaton));   //resetam automatul finit
    automaton[0] = -1;
    int j = 0;
    for (int i = 1; i < s.size(); ++i)
        {
        j = automaton [i - 1];
        while(s[i] != s[j + 1] && j!= -1)
            j = automaton[j];
        automaton[i] = j + 1;
        //if(s[i] != s[j+1])
            //automaton[i] = -1;  //punem pe fail universalg
        }
}

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 g = 0;

            for(int k = 0; k < S[j].size(); ++k)
            {
                //cout<<g<<" ("<<S[i][g]<<") "<<k<<" ("<<S[j][k]<<")\n";
                while(g != -1 && S[i][g] != S[j][k])
                    g = automaton[g];
                ++g;
                //cout<<g<<" ("<<S[i][g]<<") "<<k<<" ("<<S[j][k]<<")\n";
                if(g == S[i].size())
                {
                    gasit = 1;
                    //cout<<"MATCH FOUND!\n\n";
                    break;
                }
            }
            if(gasit)
                break;
        }
        if(!gasit)
            ret.push_back(S[i]);
    }
    return ret;
}

int potrivire(string a, string b)
{
    kmp_fail(a);
    int j = 0;

    for(int i = 0; i < b.size(); ++i)
    {
        while(j != -1 && a[j] != b[i])
            j = automaton[j];
        ++j;
    }
    return j;   //cat se potriveste a peste b la capat
}

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;
}