Cod sursa(job #2069474)

Utilizator alex2kamebossPuscasu Alexandru alex2kameboss Data 18 noiembrie 2017 14:41:26
Problema ADN Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>

using namespace std;
vector <string> adn;
vector <int> leg;
bool bun[20];
int lp[19][30];
int ma[20][20];
int n;
bool viz[20];
int v[20];
string text;
int best;
int bs[20];
int cn;
void perm(int p,int t ,long long c)
{
    if(p==n)
    {
        if(best<c)
        {
            best=c;
            for(int i=0;i<n;i++)
            {
                bs[i]=v[i];
            }
        }
        return ;
    }
    for(int i=0;i<cn;++i)
    {
        if(!viz[i])
        {
            viz[i]=1;
            v[p]=i;
            perm(p+1,i,c+ma[t][i]);
            viz[i]=0;
        }
    }
}
int main()
{
    freopen("adn.in","r",stdin);
    freopen("adn.out","w",stdout);
    scanf("%d\n", &n);
    int l;
    for(int k=0; k<n; ++k)
    {
        getline(cin,text);
        l=text.length();
        leg.push_back(l);
        adn.push_back(text);
        int j=0;
        for (int i=1; i<l; i++)
        {
            while (j>0 && text[i]!=text[j])
                j=lp[k][j-1];
            if(text[i]==text[j])
                ++j;
            lp[k][i]=j;
        }
    }
    for(int k=0; k<n; ++k)
    {
        if(!bun[k])
        {
            for(int q=0; q<n; ++q)
            {
                if(!bun[q] && k!=q)
                {
                    int j=0;
                    for(int i=0;i<leg[k];++i)
                    {
                        while(j && adn[q][j]!=adn[k][i])
                            j=lp[q][j-1];
                        if(adn[q][j]==adn[k][i])
                            ++j;
                        if(j==leg[q])
                        {
                            bun[k]=1;
                            ma[k][q]=0;
                            break;
                        }
                    }
                    ma[k][q]=j;
                }
            }
        }
    }
    for(int i=0;i<n;i++)
        if(!bun[i])
            cn++, viz[i]=1;
    swap(cn,n);
    for(int i=0;i<cn;i++)
    {
        if(!bun[i])
            viz[i]=1,v[0]=i, perm(1,i,0), viz[i]=0;
    }
    cout<<adn[bs[0]];
    for(int i=1;i<n;i++)
    {
        cout<<adn[bs[i]].substr(ma[bs[i-1]][bs[i]]);
    }
    return 0;
}