Pagini recente » Cod sursa (job #1287460) | Cod sursa (job #659219) | Cod sursa (job #1888602) | Cod sursa (job #1056853) | Cod sursa (job #1492537)
# include <bits/stdc++.h>
using namespace std;
ifstream fi("adn.in");
ofstream fo("adn.out");
char v[22][33333];
int phi[33333];
int s[22][22];
int dp[1 << 18][18];
int fr[1 << 18][18];
int len[22];
int main(void)
{
int n;
fi>>n;
for (int i = 0;i < n;++i) fi>>(v[i] + 1),len[i] = strlen(v[i] + 1);
int mask = 1 << n;--mask;
for (int i = 0;i < n;++i)
{
int k = 0;
for (int j = 2;j <= len[i];++j)
{
while (k && v[i][j] != v[i][k+1]) k = phi[k];
k += v[i][j] == v[i][k+1];
phi[j] = k;
}
for (int p = 0;p < n;++p)
if (i != p)
{
k = 0;
for (int j = 1;j <= len[p];++j)
{
while (k && v[p][j] != v[i][k+1]) k = phi[k];
k += v[p][j] == v[i][k+1];
if (k == len[i])
{
mask &= mask ^ (1 << i);
k = phi[k];
}
}
s[p][i] = len[i] - k;
}
}
int cnt = 1 << n;
for (int bit = 1;bit < cnt;++bit)
for (int j = 0;j < n;++j)
if ((bit >> j)&1)
dp[bit][j] = 2e9,fr[bit][j] = -1;
for (int i = 0;i < n;++i) dp[1 << i][i] = len[i];
for (int bit = 0;bit < cnt;++bit)
{
for (int i = 0;i < n;++i)
if ((bit >> i)&1)
for (int j = 0;j < n;++j)
if (!((bit >> j)&1))
if (dp[bit^(1<<j)][j] > dp[bit][i] + s[i][j])
{
dp[bit^(1<<j)][j] = dp[bit][i] + s[i][j];
fr[bit^(1<<j)][j] = i;
}
}
cnt = mask;
int pos = -1;
int mn = 2e9;
for (int i = 0;i < n;++i)
if (mn > dp[cnt][i] && ((cnt >> i) & 1))
mn = dp[cnt][i],pos = i;
vector < int > ans;
while (pos != -1)
{
ans.push_back(pos);
cnt ^= 1 << pos;
pos = fr[cnt | (1 << pos)][pos];
}
int siz = 0;
for (int i = 0;i < n;++i) siz += (mask >> i) & 1;
reverse(ans.begin(),ans.begin()+siz);
fo << (v[ans[0]] + 1);
for (int i = 1;i < siz;++i)
{
int l = s[ans[i-1]][ans[i]];
for (int j = len[ans[i]] - l + 1;j <= len[ans[i]];++j)
fo << v[ans[i]][j];
}
return fo << '\n',0;
}