Pagini recente » Cod sursa (job #1559993) | Cod sursa (job #1265822) | Cod sursa (job #1888326) | Cod sursa (job #2068234) | Cod sursa (job #1404595)
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;
ifstream fin("adn.in");
ofstream fout("adn.out");
const int INF = 0x3f3f3f3f;
char s[20][30005], snul[11];
int N, Ns[20], lim;
int cost[20][20], dp[263000][20], TT[263000][20];
int pi[30005];
bool used[20];
void make_prefix(char sir[])
{
int lg = strlen(sir + 1);
int k = 0;
pi[1] = 0;
for (int i = 2; i <= lg; ++i)
{
while (k > 0 && sir[k + 1] != sir[i])
k = pi[k];
if (sir[k + 1] == sir[i])
++k;
pi[i] = k;
}
}
int cost_kmp(char A[], char B[])
{
int lgA = strlen(A + 1);
int lgB = strlen(B + 1);
int k = 0;
pi[1] = 0;
for (int i = 1; i <= lgB; ++i)
{
while (k > 0 && A[k + 1] != B[i])
k = pi[k];
if (A[k + 1] == B[i])
++k;
if (k == lgA)
return lgA;
}
return k;
}
void deleteSiruri()
{
for (int i = 1; i <= N; ++i)
{
make_prefix(s[i]);
for (int j = 1; j <= N; ++j)
if (i != j && cost_kmp(s[i], s[j]) == Ns[i])
{
used[i] = true;
break;
}
}
}
void makeCost()
{
for (int i = 1; i <= N; ++i)
{
if (used[i])
continue;
make_prefix(s[i]);
for (int j = 1; j <= N; ++j)
{
if (used[j] || i == j)
continue;
//cost[i][j] = cost_kmp(s[i], s[j]);
cost[j][i] = cost_kmp(s[i], s[j]);
}
}
}
void path(int pos, int l)
{
if (!TT[l][pos])
{
for (int i = 1; i <= Ns[pos]; ++i)
fout << s[pos][i];
return;
}
path(TT[l][pos], l - (1 << (pos - 1)));
for (int i = cost[TT[l][pos]][pos] + 1; i <= Ns[pos]; ++i)
fout << s[pos][i];
}
void solve()
{
for (int i = 1; i <= (1 << N); ++i)
for (int j = 1; j <= N; ++j)
dp[i][j] = INF;
for (int i = 1; i <= N; ++i)
if (!used[i])
dp[1 << (i - 1)][i] = Ns[i];
lim = 0;
for (int i = 1; i <= N; ++i)
if (!used[i])
lim += (1 << (i - 1));
for (int mask = 1; mask <= (1 << N); ++mask)
{
for (int i = 1; i <= N; ++i)
{
if (used[i])
continue;
if (mask & (1 << (i - 1)))
{
for (int j = 1; j <= N; ++j)
{
if (used[j] || i == j)
continue;
if (mask & (1 << (j - 1)))
{
if (dp[mask - (1 << (i - 1))][j] + Ns[i] - cost[j][i] < dp[mask][i])
{
dp[mask][i] = dp[mask - (1 << (i - 1))][j] + Ns[i] - cost[j][i];
TT[mask][i] = j;
}
//dp[mask][i] = min(dp[mask][i], dp[mask - (1 << (i - 1))][j] + Ns[i] - cost[j][i]);
}
}
}
}
}
int maxim = INF, pos;
for (int i = 1; i <= N; ++i)
if (dp[lim][i] < maxim)
{
maxim = dp[lim][i];
pos = i;
}
path(pos, lim);
}
int main()
{
fin >> N;
fin.getline(snul, 11);
for (int i = 1; i <= N; ++i)
fin.getline(s[i] + 1, 30005);
for (int i = 1; i <= N; ++i)
Ns[i] = strlen(s[i] + 1);
deleteSiruri();
makeCost();
solve();
fin.close();
fout.close();
return 0;
}