Pagini recente » Cod sursa (job #1122769) | Cod sursa (job #766612) | Cod sursa (job #3285056) | Cod sursa (job #143334) | Cod sursa (job #3247069)
#include <bits/stdc++.h>
const std :: string FILENAME = "adn";
std :: ifstream f (FILENAME + ".in");
std :: ofstream g (FILENAME + ".out");
const int NMAX = 18;
const int DIM = 3e4 + 5;
const int INF = 1e9;
short n;
int cnt;
bool ok;
std :: vector <short> pi(2 * DIM);
std :: vector <std :: string> v(NMAX);
std :: bitset <NMAX> fr;
std :: vector <std :: vector <short>> dist(NMAX, std :: vector <short>(NMAX));
std :: vector <std :: vector <std :: string>> dp((1 << NMAX), std :: vector <std :: string>(NMAX));
inline short pref(std :: string a, std :: string b)
{
std :: string s = b + "#" + a;
for(int i = 1; i < s.size(); i ++)
{
short j = pi[i - 1];
while(j > 0 && s[i] != s[j])
{
j = pi[j - 1];
}
if(s[i] == s[j])
{
j ++;
}
pi[i] = j;
}
short k = pi[s.size() - 1];
return k;
}
inline bool continut(std :: string a, std :: string b)
{
std :: string s = a + "#" + b;
for(int i = 1; i < s.size(); i ++)
{
short j = pi[i - 1];
while(j > 0 && s[i] != s[j])
{
j = pi[j - 1];
}
if(s[i] == s[j])
{
j ++;
}
pi[i] = j;
}
for(int i = 0; i < s.size(); i ++)
{
if(pi[i] == a.size())
{
return true;
}
}
return false;
}
int main()
{
f >> n;
for(short i = 0; i < n; i ++)
{
f >> v[i];
}
for(short i = 0; i < n; i ++)
{
ok = true;
for(short j = 0; j < n; j ++)
{
if(i == j)
{
continue;
}
if(continut(v[i], v[j]))
{
ok = false;
break;
}
}
fr[i] = ok;
}
for(short i = 0; i < n; i ++)
{
if(fr[i])
{
v[cnt ++] = v[i];
}
}
n = cnt;
for(short i = 0; i < n; i ++)
{
for(short j = 0; j < n; j ++)
{
if(i == j)
{
continue;
}
dist[i][j] = pref(v[i], v[j]);
}
}
for(short i = 0; i < n; i ++)
{
dp[(1 << i)][i] = v[i];
}
for(int mask = 0; mask < (1 << n); mask ++)
{
for(short i = 0; i < n; i ++)
{
if(mask & (1 << i))
{
for(short j = 0; j < n; j ++)
{
if((mask ^ (1 << i)) & (1 << j))
{
if((dp[mask][i].size() == 0) || ((int)dp[mask ^ (1 << i)][j].size() + (int)v[i].size() - dist[j][i] + 1 < (int)dp[mask][i].size()))
{
dp[mask][i] = dp[mask ^ (1 << i)][j] + v[i].substr(dist[j][i]);
}
}
}
}
}
}
cnt = INF;
for(short i = 0; i < n; i ++)
{
cnt = std :: min(cnt, (int)dp[(1 << n) - 1][i].size());
}
for(short i = 0; i < n; i ++)
{
if((int)dp[(1 << n) - 1][i].size() == cnt)
{
g << dp[(1 << n) - 1][i];
return 0;
}
}
return 0;
}