Pagini recente » Cod sursa (job #2978441) | Cod sursa (job #123252) | Cod sursa (job #2968854) | Cod sursa (job #56228) | Cod sursa (job #2961836)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#define MAXN (1 << 18)
#define oo 0x3f3f3f3f
using namespace std;
ifstream fin("adn.in");
ofstream fout("adn.out");
int n, minim = oo, poz;
vector<string> text;
int pi[30005];
int C[MAXN + 5][20], Cost[20][20];
void compute(string cuv)
{
int q = 0;
pi[1] = 0;
for (int i = 2; i <= cuv.length(); i++)
{
while (q && cuv[q] != cuv[i - 1])
q = pi[q];
if (cuv[q] == cuv[i - 1])
q++;
pi[i] = q;
}
}
int KMP(string cuv1, string cuv2)
{
int q = 0;
for (int i = 1; i <= cuv2.length(); i++)
{
while (q && cuv1[q] != cuv2[i - 1])
q = pi[q];
if (cuv1[q] == cuv2[i - 1])
++q;
if (q == cuv1.length() - 1)
return 0;
}
return cuv1.length() - q;
}
void reconstruct(int mask, int varf)
{
if ((mask & (mask - 1)) == 0)
{
for (int i = 0; i < n; ++i)
if ((1 << i) == mask)
{
fout << text[i];
return;
}
}
int mask2 = mask ^ (1 << varf);
for (int i = 0; i < n; ++i)
{
if (C[mask][varf] == C[mask2][i] + Cost[i][varf])
{
reconstruct(mask2, i);
fout << text[varf].substr(text[varf].length() - Cost[i][varf]);
return;
}
}
}
void lant()
{
for (int mask = 1; mask < (1 << n); ++mask)
for (int pos = 0; pos < n; ++pos)
if (mask & (1 << pos))
{
int mask2 = mask ^ (1 << pos);
if (mask2 == 0)
{
C[mask][pos] = text[pos].length();
break;
}
for (int j = 0; j < n; ++j)
if (mask2 & (1 << j))
C[mask][pos] = min(C[mask][pos], C[mask2][j] + Cost[j][pos]);
}
for (int i = 0; i < n; ++i)
if (C[(1 << n) - 1][i] < minim)
minim = C[(1 << n) - 1][i], poz = i;
reconstruct((1 << n) - 1, poz);
}
int main()
{
fin >> n;
string s;
for (int i = 0; i < n; i++)
fin >> s, text.push_back(s);
memset(C, oo, sizeof(C));
bool gasit = false;
do {
gasit = false;
for (int i = 0; i < n; ++i)
{
compute(text[i]);
for (int j = 0; j < n; ++j)
if (i != j && !(KMP(text[i], text[j])))
{
n--;
gasit = true;
text.erase(text.begin() + i);
}
}
} while (gasit);
for (int i = 0; i < n; i++)
{
compute(text[i]);
for (int j = 0; j < n; j++)
if (i != j)
Cost[j][i] = KMP(text[i], text[j]);
}
lant();
return 0;
}