Pagini recente » Cod sursa (job #3240516) | Cod sursa (job #265339) | Cod sursa (job #3169427) | Cod sursa (job #79578) | Cod sursa (job #3036594)
#include <fstream>
#include <string>
#include <vector>
#pragma GCC optimize ("Ofast")
using namespace std;
#define inf 0x3f3f3f3f
ifstream fin("adn.in");
ofstream fout("adn.out");
string s[20], a;
int p[60001], c[20][20], r[20];
int n, x, rasp[20];
vector <int> v[20];
pair <int, int> dp[262300][20];
bool kmp (int x, int y)
{
int k;
a = s[y] + '#' + s[x];
for(int i = 1; i < (int) a.size(); i++)
{
k = p[i - 1];
while (k > 0 && a[i] != a[k])
k = p[k - 1];
if (a[i] == a[k])
k++;
p[i] = k;
if (p[i] == (int) s[y].size())
return 1;
}
c[x][y] = (int) s[y].size() - (int) p[a.size() - 1];
return 0;
}
int calc()
{
int m = 0, i, j;
bool ok[18] = {};
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (i != j)
ok[j] = ok[j] | kmp(i, j);
for (i = 0; i<n; i++)
if (ok[i] == 0)
{
r[m] = i;
m++;
}
return m;
}
int main()
{
fin >> n;
for(int i = 0; i < n; i++)
fin >> s[i];
n = calc();
for(int i = 0; i < (1 << n); i++)
v[__builtin_popcount(i)].push_back(i);
for(int i = 0; i < n; i++)
dp[1 << i][i] = { (int) s[r[i]].size(), -1};
for(int i = 2; i <= n; i++)
for(int j = 0; j < (int) v[i].size(); j++)
{
x = v[i][j];
for(int k = 0; k < n; k++)
if (x & (1 << k))
{
dp[x][k] = {inf, 0};
for(int y = 0; y < n; y++)
if ((x ^ (1 << k)) & (1 << y))
dp[x][k] = min(dp[x][k], {dp[x ^ (1<<k)][y].first + c[r[y]][r[k]], y});
}
}
x = 0;
for(int i = 1; i < n; i++)
if (dp[(1 << n) - 1][i].first < dp[(1 << n) - 1][x].first)
x = i;
for(int i = x, j = (1<<n)-1; i != -1; j = j ^ (1<<i), i = dp[j ^ (1<<i)][i].second)
rasp[++rasp[0]] = i;
fout << s[r[rasp[rasp[0]]]];
for(int i = rasp[0] - 1; i >= 1; i--)
{
x = c[r[rasp[i + 1]]][r[rasp[i]]];
for(int j = (int) s[r[rasp[i]]].size() - x; j < (int) s[r[rasp[i]]].size(); j++)
fout << s[r[rasp[i]]][j];
}
return 0;
}