Cod sursa(job #2985028)

Utilizator gabriel10tm@gmail.comGabriel Marian [email protected] Data 25 februarie 2023 15:30:03
Problema ADN Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <bits/stdc++.h>
using namespace std;
#if 1
#define cin fin
#define cout fout
ifstream fin("adn.in");
ofstream fout("adn.out");
#endif // 1
vector<int> calcPi(string& s){
    vector<int> pi(s.size());
    int j=0;
    for(int i=1;i<s.size();i++){
        while(j>0 && s[i]!=s[j])
            j = pi[j-1];
        if(s[i]==s[j])
            j++;
        pi[i] = j;
    }
    return pi;
}

int _conc(string& s1,string& s2){
    string c = s1 + s2;
    vector<int> pi = calcPi(c);
    return pi[c.size()-1];
}

string concat(string& s1,string& s2){
    if(s1==s2)
        return s1;
    if(s1.find(s2)!=string::npos)
        return s1;
    if(s2.find(s1)!=string::npos)
        return s2;
    int r1 = _conc(s1,s2);
    int r2 = _conc(s2,s1);
    if(r1 > r2){
        return s2 + s1.substr(r1);
    }
    else {
        return s1 + s2.substr(r2);
    }
}

int main(){
    int n;
    cin >> n;
    vector<string> vs(n);
    for(int i=0;i<n;i++)
        cin >> vs[i];
    string res = vs.back();
    vs.pop_back();
    for(int i=1;i<n;i++){
        int mni=0;
        string mns = concat(res,vs[0]);
        for(int j=1;j<vs.size();j++){
            string c = concat(res,vs[j]);
            if(c.size()<mns.size()){
                mns = move(c);
                mni = j;
            }
        }
        vs.erase(vs.begin()+mni);
        res = mns;
    }
    cout << res;
}