Cod sursa(job #2957221)

Utilizator DafinaTrufasTrufas Dafina DafinaTrufas Data 21 decembrie 2022 23:18:02
Problema ADN Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.29 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

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

string longestCommonSubsequence(string text1, string text2) {
        int i, j;
        vector<vector<string> > m(2, vector<string>(text2.length() + 1, ""));
        for (i = 0; i < text1.length(); i++)
            for (j = 0; j < text2.length(); j++)
            {
                if (text1[i] == text2[j])
                {
                    if (i % 2 == 0)
                        m[1][j + 1] = m[0][j] + text1[i];
                    else m[0][j + 1] = m[1][j] + text1[i];
                }
                else
                {
                    if (i % 2 == 0)
                    {
                        if (m[0][j + 1].length() > m[1][j].length())
                            m[1][j + 1] = m[0][j + 1];
                        else m[1][j + 1] = m[1][j];
                    }
                    else
                    {
                        if (m[1][j + 1].length() > m[0][j].length())
                            m[0][j + 1] = m[1][j + 1];
                        else m[0][j + 1] = m[0][j];
                    }
                }
            }
        if (text1.length() % 2 == 0)
            return m[0][text2.length()];
        return m[1][text2.length()];
    }

string shortestCommonSupersequence(string text1, string text2) {
        int i, j = 0, k = 0;
        string superseq = "", subseq = longestCommonSubsequence(text1, text2);
        for (i = 0; i < subseq.length(); i++)
        {
            while (text1[j] != subseq[i])
            {
                superseq += text1[j];
                j++;
            }
            while (text2[k] != subseq[i])
            {
                superseq += text2[k];
                k++;
            }
            superseq += subseq[i];
            j++;
            k++;
        }
        return superseq + text1.substr(j) + text2.substr(k);
    }

int main()
{int n, i;
string s, t, rez;
f >> n;
if (n == 1)
{
    f >> s;
    g << s;
}
else
{
    f >> s >> t;
    rez = shortestCommonSupersequence(s, t);
    for (i = 2; i < n; i++)
    {
        f >> s;
        rez = shortestCommonSupersequence(rez, s);
    }
    g << rez;
}
return 0;
}