Pagini recente » Cod sursa (job #1880291) | Cod sursa (job #71661) | Cod sursa (job #3281941) | Cod sursa (job #226857) | Cod sursa (job #2969163)
#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;
}