Pagini recente » Cod sursa (job #3360050) | Cod sursa (job #3360013) | Cod sursa (job #3360034) | Cod sursa (job #3360037) | Cod sursa (job #3360030)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <string>
#define inf 1e9+1
using namespace std;
ifstream fin("adn.in");
ofstream fout("adn.out");
vector<string>v;
int n;
const int NMAX = 16;
int c[NMAX][NMAX];//c[i][j]=cat trebuie sa adaugam ca sa formam un sir concatenat din (i,j)
//c[i][j]= v[i].size()- cel mai lung sufix din j care e prefix in i
//pentru asta lipim v[i] apoi v[j] si aplicam KMP
//(nvm ,l-am facut invers)
const int NMAX2 = (1 << NMAX) + 2;
int dp[NMAX][NMAX2];
//dp[i][mask] = lungimea minima a unui sir pe care putem forma stiinda ca ultimul sir gasit ca si potrivire este sirul i si avem deja sirurile din mask acoperite
void removeUselessElements() {
vector<int>removeElements;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i != j && v[i].size() >= v[j].size()) {
if (v[i].find(v[j]) != string::npos) {
removeElements.push_back(j);
}
}
}
}
sort(removeElements.begin(), removeElements.end());
removeElements.erase(unique(removeElements.begin(), removeElements.end()), removeElements.end());
for (int i = removeElements.size() - 1; i >= 0; --i) {
v.erase(v.begin() + removeElements[i]);
}
}
int calcLungComun(string& s) {
vector<int>pi(s.size() + 1);
pi[1] = 0;
int k = 0;
for (int i = 2; i <= s.size(); ++i) {
while (k != 0 && s[k] != s[i - 1]) {
k = pi[k];
}
if (s[k] == s[i - 1]) {
k++;
}
pi[i] = k;
}
return pi[s.size()];
}
void calcC() {
string aux;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
aux = v[j] + '%' + v[i];
c[i][j] = v[j].size() - calcLungComun(aux);
// fout << i << " " << j << " " << c[i][j]<<endl;
}
}
}
void calcDp() {
for (int i = 0; i < NMAX; ++i) {
for (int j = 0; j < NMAX2; ++j) {
dp[i][j] = inf;
}
}
for (int i = 0; i < n; ++i) {
dp[i][1 << i] = v[i].size();//lungimea propriilor siruri e lungimea insasi
}
for (int m = 1; m <= (1 << n); ++m) {
for (int i = 0; i < n; ++i) {
if (m & (1 << i)) {//daca i face parte din masca curenta
for (int j = 0; j < n; ++j) {
if (!(m & (1 << j))) {//daca nu l-am inclus deja pe j
//il adugam pe j la masca curenta
int nextMask = m + (1 << j);
dp[j][nextMask] = min(dp[j][nextMask], dp[i][m] + c[i][j]);
}
}
}
}
}
}
void getResult() {
int rez=inf;
int lastMask = (1 << n) - 1;
int lastIndex;
for (int i = 0; i < n; ++i) {
if (rez > dp[i][lastMask]) {
rez = dp[i][lastMask];
lastIndex = i;//ultimul indice care face parte din masca
}
}
vector<int> indexStrings;
indexStrings.push_back(lastIndex);
for(int i=1;i<n;++i) {
int nextMask = lastMask - (1 << lastIndex);
for (int j = 0; j < n; ++j) {
if (nextMask & (1 << j) && j!=lastIndex) {
if (dp[lastIndex][lastMask] == dp[j][nextMask] + c[j][lastIndex]) {//daca j e urmatoarul string din permutare
// cout << "test!!!!";
lastMask = nextMask;
lastIndex = j;
indexStrings.push_back(j);
j = n;
}
}
}
}
//cout << indexStrings.size() << endl;
reverse(indexStrings.begin(), indexStrings.end());
fout << v[indexStrings[0]];
for (int i = 1; i < indexStrings.size(); ++i) {
int ant = indexStrings[i - 1];
int crt = indexStrings[i];
int intersectie = v[crt].size()-c[ant][crt];
for (int j = intersectie; j < v[crt].size(); ++j) {
fout << v[crt][j];
}
}
return ;
}
int main()
{
fin >> n;
v.resize(n);
for (int i = 0; i < n; ++i) {
fin >> v[i];
}
removeUselessElements();
n = v.size();
calcC();
calcDp();
getResult();
return 0;
}
//=^..^=