Pagini recente » Cod sursa (job #2615289) | Cod sursa (job #418120) | Cod sursa (job #1134036) | Cod sursa (job #461015) | Cod sursa (job #2771710)
#include <fstream>
#include <cstring>
#include <vector>
#include <string>
using namespace std;
const int NMAX = 18;
const int LMAX = 30001;
const int INF = 1000000;
string cuvinte[NMAX];
string s;
int prefix[5 + 2 * LMAX];
bool inclus[1 + NMAX];
vector<pair<int, int>> graf[NMAX];
int dp[1 << NMAX][NMAX];
pair<int, int> last[1 << NMAX][NMAX];
void kmp(int i, int j)
{
memset(prefix, 0, sizeof(prefix));
s = ' ' + cuvinte[i] + '$' + cuvinte[j];
int pi = 0;
for (int l = 2; l < s.size(); l++)
{
while (pi > 0 && s[l] != s[pi + 1])
pi = prefix[pi];
if (s[l] == s[pi + 1])
pi++;
prefix[l] = pi;
if (pi == cuvinte[i].size())
inclus[i] = true;
}
graf[i].emplace_back(make_pair(j, cuvinte[i].size() - prefix[s.size() - 1]));
}
string makeSol(int bitMask, int nod)
{
if (bitMask == 0)
return "";
string s = makeSol(bitMask - (1 << nod), last[bitMask][nod].first);
for (int i = cuvinte[nod].size() - last[bitMask][nod].second; i < cuvinte[nod].size(); i++)
s += cuvinte[nod][i];
return s;
}
int main()
{
ifstream in("adn.in");
ofstream out("adn.out");
int n;
in >> n;
for (int i = 0; i < n; i++)
in >> cuvinte[i];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (i != j)
kmp(i, j);
for (int bitMask = 0; bitMask < (1 << n); bitMask++)
for (int nod = 0; nod < n; nod++)
dp[bitMask][nod] = INF;
for (int nod = 0; nod < n; nod++)
{
dp[1 << nod][nod] = cuvinte[nod].size();
last[1 << nod][nod] = make_pair(-1, cuvinte[nod].size());
}
for (int bitMask = 0; bitMask < (1 << n); bitMask++)
for (int nod = 0; nod < n; nod++)
if (!inclus[nod] && (bitMask & (1 << nod)) != 0)
for (auto& vecin : graf[nod])
if (!inclus[vecin.first] && (bitMask & (1 << vecin.first)) != 0)
if (dp[bitMask][nod] > dp[bitMask - (1 << nod)][vecin.first] + vecin.second)
{
dp[bitMask][nod] = dp[bitMask - (1 << nod)][vecin.first] + vecin.second;
last[bitMask][nod] = vecin;
}
int sol = INF;
int solMask = (1 << n) - 1;
int solNod = -1;
for (int i = 0; i < n; i++)
if (inclus[i])
solMask -= (1 << i);
for (int i = 0; i < n; i++)
if (!inclus[i] && sol > dp[solMask][i])
{
sol = min(sol, dp[solMask][i]);
solNod = i;
}
out << makeSol(solMask, solNod) << '\n';
return 0;
}