Cod sursa(job #2884325)

Utilizator error1000Udrea Dan Mihai error1000 Data 2 aprilie 2022 21:28:15
Problema ADN Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <bits/stdc++.h>
#include <fstream>

using namespace std;

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


unsigned int overlaps(string& s1, string& s2, int offset2){
    unsigned int amnt = 0;
    for(int i = offset2, j = 0; i < (int)s1.size() && j < s2.size(); i++, j++)
        if(i >= 0 && j >= 0){
            if(s1[i] != s2[j]) return false; else amnt++;
        } 
    return amnt;
}

string merge(string res, string to_merge, int merge_ind){
    if(merge_ind >= 0){
        int j = 0;
        for(int i = merge_ind; i < res.size(); i++){
            res[i] = to_merge[j];
            j++;
            if(j >= to_merge.size()) return res;
        }
        res.append(to_merge.substr(j));
        return res;
    }else{
        return merge(to_merge, res, -merge_ind);
    }
}
int main() {
    unsigned int n;
    in >> n;
    vector<string> parti;
    for(int i = 0; i < n; i++){
        string t;
        in >> t;
        parti.push_back(t);
    }
    string complet = parti.back();
    parti.pop_back();

    while(parti.size() != 0){
        int merge_loc = 0;
        int merge_ind = 0;
        int merge_amount = 0;
        for(int i = 0; i < parti.size(); i++){
            for(int j = -parti[i].size()+1; j < (int)complet.size(); j++){
                unsigned int amount = overlaps(complet, parti[i], j);
                if(amount == parti[i].size()){
                    merge_amount = amount;
                    merge_ind = i;
                    merge_loc = j;
                    break;
                }
                if(amount > merge_amount){
                    merge_amount = amount;
                    merge_ind = i;
                    merge_loc = j;
                }
            }
        }
        string to_merge = parti[merge_ind];
        parti.erase(parti.begin()+merge_ind);
        complet = merge(complet, to_merge, merge_loc);
    }
    out << complet << endl;
}