Pagini recente » Cod sursa (job #2194283) | Cod sursa (job #505382) | Cod sursa (job #2998359) | Cod sursa (job #629479) | Cod sursa (job #2957221)
#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;
}