Cod sursa(job #2470023)

Utilizator bluestorm57Vasile T bluestorm57 Data 8 octombrie 2019 17:08:52
Problema ADN Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.03 kb
//wish me luck
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 30005;
const int LMAX = 20;
vector < string > v;
string s;
int t,pi[NMAX],n,mat[LMAX][LMAX];
int vf[LMAX], st[LMAX];
int ans[LMAX],ansl;

void make_prefix(int i){
    int q = 0,j;
    pi[1] = 0;
    for(j = 2 ; j <= n ; j++){
        while(q && v[i][q + 1] != v[i][j])
            q = pi[q];
        if(v[i][q + 1] == v[i][j])
            q++;
        pi[j] = q;
    }
}

bool is_somewhere(int x){
    int j,q,i,m;
    for(j = 0 ; j < v.size() ; j++)
        if(x != j){
            q = 0;
            m = v[j].size() - 1;
            for(i = 1 ; i <= m ; i++){
                while(q && v[x][q + 1] != v[j][i])
                    q = pi[q];
                if(v[x][q + 1] == v[j][i])
                    q++;
                if(q == n)
                    return 1;
            }
        }
    return 0;
}

int solutie;
void beckateu(int k){
    if(k == v.size() + 1){
        if(solutie > ansl){
            ansl = solutie;
            for(int i = 1 ; i < k ; i++)
                ans[i] = st[i];
        }
        return;
    }
    if(k == 1){
        for(int i = 0 ; i < v.size() ; i++){
            st[k] = i;
            vf[i] = 1;
            beckateu(k + 1);
            vf[i] = 0;
        }
        return;
    }
    for(int i = 0 ; i < v.size() ; i++)
        if(!vf[i]){
            vf[i] = 1;
            solutie += mat[st[k - 1]][i];
            st[k] = i;
            beckateu(k + 1);
            solutie -= mat[st[k - 1]][i];
            vf[i] = 0;
        }

}

int main(){
    int i,j,q,ii,jj,k;
    f >> t;
    for(i = 1 ; i <= t ; i++){
        f >> s;
        s = ' ' + s;
        v.push_back(s);
        s.clear();
    }

    for(i = 0 ; i < v.size() ; i++){
        n = v[i].size() - 1;
        make_prefix(i);
        if(is_somewhere(i))
            v.erase(v.begin() + i);
    }

    int maxx = 0;
    for(i = 0 ; i < v.size() ; i++)
        for(j = i + 1 ; j < v.size() ; j++)
            if(i != j){
                q = 0;
                pi[1] = 0;
                for(ii = 2 ; ii < v[i].size() ; ii++){
                    while(q && v[i][ii] != v[j][q + 1])
                        q = pi[q];
                    if(v[i][ii] == v[j][q + 1])
                        q++;
                    pi[ii] = q;
                }
                mat[i][j] = q;

                q = 0;
                pi[1] = 0;
                for(jj = 2 ; jj < v[j].size() ; jj++){
                    while(q && v[j][jj] != v[i][q + 1])
                        q = pi[q];
                    if(v[j][jj] == v[i][q + 1])
                        q++;
                    pi[jj] = q;
                }
                mat[j][i] = q;
        }

    beckateu(1);
    g << v[ans[1]];
    for(i = 2 ; i <= v.size() ; i++){
        for(j = mat[ans[i - 1]][ans[i]] + 1 ; j < v[ans[i]].size() ; j++)
            g << v[ans[i]][j];
    }

    return 0;
}