Pagini recente » Cod sursa (job #9218) | Cod sursa (job #2400849) | Cod sursa (job #2177918) | Cod sursa (job #1760340) | Cod sursa (job #356879)
Cod sursa(job #356879)
#include <algorithm>
#include <stdio.h>
#include <vector>
#include <string>
#define MAX 32000
#define pb push_back
using namespace std;
int n, minGs = LONG_MAX, loc, poz;
int pi[MAX];
int up[20][20];
char strConf[20][MAX];
vector <string> strAdn;
int lungSol[(1 << 18)][20];
inline void prefix(string str)
{
int k = 0;
for (int i = 2; i < str.size(); i++)
{
for (; k && str[i] != str[k + 1]; k = pi[k]);
if (str[i] == str[k + 1])
k++;
pi[i] = k;
}
}
inline int kmp(string strMic, string strMare)
{
prefix(strMic);
int k = 0, incl = 0;
for (int i = 1; i < strMare.size(); i++)
{
for (; k && strMare[i] != strMic[k + 1]; k = pi[k]);
if (strMare[i] == strMic[k + 1])
k++;
if (k == strMic.size() - 1)
{
k = pi[k];
incl = 1;
}
}
poz = k;
return incl;
}
inline void afis(int conf, int loc)
{
int cf = conf - (1 << loc);
int puse = 0;
for (int ul = 0; ul < n; ul++)
if (lungSol[cf][ul] + strAdn[loc].size() - 1 - up[ul][loc] == lungSol[conf][loc])
{
afis(cf, ul);
for (int i = up[ul][loc] + 1; i < strAdn[loc].size(); i++)
printf("%c", strAdn[loc][i]);
return;
}
for (int i = 1; i < strAdn[loc].size(); i++)
printf("%c", strAdn[loc][i]);
}
int main()
{
freopen("adn.in", "r", stdin);
freopen("adn.out", "w", stdout);
scanf("%d\n", &n);
for (int i = 1; i <= n; i++)
{
fgets(strConf[i] + 1, MAX, stdin);
strConf[i][strlen(strConf[i] + 1)] = 0;
strConf[i][0] = '-';
}
for (int i = 1; i <= n; i++)
{
strAdn.pb(strConf[i]);
for (int j = 1; j <= n; j++)
if (i != j)
if (kmp(strConf[i], strConf[j]))
{
strAdn.pop_back();
break;
}
}
n = strAdn.size();
for (int i = 0; i < (1 << n); i++)
for (int j = 0; j < n; j++)
lungSol[i][j] = LONG_MAX;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
kmp(strAdn[i], strAdn[j]);
up[i][j] = poz;
}
lungSol[1 << i][i] = strAdn[i].size() - 1;
}
for (int conf = 1; conf < (1 << n); conf++)
for (int ul = 0; ul < n; ul++)
if (conf & (1 << ul))
for (int pun = 0; pun < n; pun++)
if (!(conf & (1 << pun)))
lungSol[conf | (1 << pun)][pun] = min((unsigned) lungSol[conf | (1 << pun)][pun],
lungSol[conf][ul] + strAdn[pun].size() - 1 - up[ul][pun]);
for (int i = 0; i < n; i++)
if (lungSol[(1 << n) - 1][i] < minGs)
{
minGs = lungSol[(1 << n) - 1][i];
loc = i;
}
afis((1 << n) - 1, loc);
fclose(stdin);
fclose(stdout);
return 0;
}