Cod sursa(job #2969163)

Utilizator NefelibataAnton Marius Alexandru Nefelibata Data 22 ianuarie 2023 17:16:29
Problema ADN Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.71 kb
#include <iostream>
#include <bits/stdc++.h>
#include <fstream>

using namespace std;

string longestSubsequence(string str1, string str2) {
    string str3 = str1;
    string str4 = str2;
    string S;
    unsigned int match_max = 0;
    while (str4.length()) {
        size_t found = str3.find(str4);
        if (found != string::npos) {
            match_max = str4.length();
            S = str4;
            break;
        }
        str4.pop_back();
    }
    str3 = str1;
    str4 = str2;
    while (str4.length() > match_max) {
        size_t found = str3.find(str4);
        if (found != string::npos) {
            match_max = str4.length();
            S = str4;
            break;
        }
        str4.erase(0, 1);
    }
    str3 = str1;
    str4 = str2;
    while (str3.length() > match_max) {
        size_t found = str4.find(str3);
        if (found != string::npos) {
            match_max = str3.length();
            S = str3;
            break;
        }
        str3.pop_back();
    }
    str3 = str1;
    str4 = str2;
    while (str3.length() > match_max) {
        size_t found = str4.find(str3);
        if (found != string::npos) {
            match_max = str3.length();
            S = str3;
            break;
        }
        str3.erase(0, 1);
    }
    return S;
}

string shortestCommonSupersequence(string str1, string str2) {
    /*
    int L[str1.length()+1][str2.length()+1];
    for (int i = str1.length(); i >= 0; --i)
        for (int j = str2.length(); j >= 0; --j) {
            if (str1[i] == '\0' || str2[j] == '\0') L[i][j] = 0;
            else if (str1[i] == str2[j]) L[i][j] = 1 + L[i+1][j+1];
            else L[i][j] = max(L[i+1][j], L[i][j+1]);
        }
    string S = "";
    unsigned int i = 0;
    unsigned int j = 0;
    while (i < str1.length() && j < str2.length()) {
        if (str1[i] == str2[j]) {
            S += str1[i];
            ++i;
            ++j;
        } else if (L[i+1][j] >= L[i][j+1]) ++i;
        else ++j;
    }
    */
    string S = longestSubsequence(str1, str2);
    unsigned int i = 0;
    unsigned int j = 0;
    string S2 = "";
    size_t found = str1.find(S);
    size_t found2 = str2.find(S);
    if (found == string::npos) return "0";
    else if (found2 == string::npos) return "0";
    else if (found && found2) return "0";
    else if (found) {
        while (found) {
            S2 += str1[i];
            --found;
            ++i;
        }
    } else if (found2) {
        while (found2) {
            S2 += str2[j];
            --found2;
            ++j;
        }
    }

    S2 += S;
    i += S.length();
    j += S.length();

    while (i < str1.length()) {
        S2 += str1[i++];
    }
    while (j < str2.length()) {
        S2 += str2[j++];
    }
    return S2;
}

int main() {
    ifstream f("adn.in");
    ofstream o("adn.out");
    int n;
    f>>n;
    vector<string> t(n);
    for (int i = 0; i < n; ++i) {
        f>>t[i];
    }

    int k = 0;
    for (int j = 0; j < n-1; ++j) {
        int best_match_index = 1;
        unsigned int best_match = 0;
        for (int i = 1; i < n-k; ++i) {
            if (longestSubsequence(t[0], t[i]).length() > best_match) {
                best_match = longestSubsequence(t[0], t[i]).length();
                best_match_index = i;
            }
        }
        ++k;
        string t0 = shortestCommonSupersequence(t[0], t[best_match_index]);
        t[0] = t0;
        t.erase (t.begin() + best_match_index);
    }
    /*
    for (int i = 1; i < 5; ++i) {
        cout<<t[0]<<endl<<t[i]<<endl;
        cout<<shortestCommonSupersequence(t[0], t[i])<<endl<<endl;
    }*/
    o<<t[0];

    return 0;
}