Pagini recente » Cod sursa (job #528985) | Cod sursa (job #2397028) | Cod sursa (job #866004) | Cod sursa (job #972397) | Cod sursa (job #2511347)
#include <bits/stdc++.h>
using namespace std;
ifstream in("adn.in");
ofstream out("adn.out");
const int DIM = 30017;
struct Sir
{
int l;
string s;
int prefix[DIM];
void add(string p)
{
memset(prefix, 0, sizeof(prefix));
l = p.size();
s = ' ' + p;
int k = 0;
for(int i = 2; i <= l; i++)
{
while(k != 0 && s[k + 1] != s[i])
k = prefix[k];
if(p[k + 1] == s[i])
k++;
prefix[i] = k;
}
}
bool este(Sir x)
{
int k = 0;
for(int i = 1; i <= x.l; i++)
{
while(k != 0 && s[k + 1] != x.s[i])
k = prefix[k];
if(s[k + 1] == x.s[i])
k++;
if(k == l)
return true;
}
return false;
}
int cost(Sir x)
{
int k = 0;
for(int i = 1; i <= x.l; i++)
{
while(k != 0 && s[k + 1] != x.s[i])
k = prefix[k];
if(s[k + 1] == x.s[i])
k++;
}
return l - k;
}
void print(int nr)
{
for(int i = l - nr + 1; i <= l; i++)
out << s[i];
}
};
Sir v[20];
Sir t[20];
bool cmp(Sir a, Sir b)
{
return (a.l < b.l);
}
int n;
void read()
{
in >> n;
for(int i = 0; i < n; i++)
{
string temp;
in >> temp;
v[i].add(temp);
}
for(int i = 0; i < n - 1; i++)
for(int j = i + 1; j < n; j++)
if(v[i].l > v[j].l)
swap(v[i], v[j]);
}
void del()
{
int k = 0;
for(int i = 0; i < n; i++)
{
bool ok = false;
for(int j = i + 1; j < n; j++)
if(v[i].este(v[j]))
{
ok = true;
break;
}
if(ok == false)
t[k++] = v[i];
}
n = k;
}
int c[20][20];
void getCosts()
{
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if(i != j)
c[j][i] = t[i].cost(t[j]);
}
int dp[(1 << 19)][19];
int from[(1 << 19)][19];
const int INF = 1e8;
void init()
{
for(int i = 0; i < (1 << n); i++)
for(int j = 0; j < n; j++)
dp[i][j] = INF;
}
void calcAns()
{
init();
for(int i = 0; i < n; i++)
dp[(1 << i)][i] = t[i].l;
for(int i = 0; i < (1 << n); i++)
for(int j = 0; j < n; j++)
if(i & (1 << j))
for(int k = 0; k < n; k++)
if(i & (1 << k))
if(dp[i][j] > dp[i ^ (1 << j)][k] + c[k][j])
{
dp[i][j] = dp[i ^ (1 << j)][k] + c[k][j];
from[i][j] = k;
}
}
void printAns()
{
int all = (1 << n) - 1;
int start = 0;
for(int i = 1; i < n; i++)
if(dp[all][i] < dp[all][start])
start = i;
vector <int> path;
int now = start;
while(all > 0)
{
path.push_back(now);
int urm = from[all][now];
all ^= (1 << now);
now = urm;
}
reverse(path.begin(), path.end());
t[path[0]].print(t[path[0]].l);
for(int i = 1; i < path.size(); i++)
t[path[i]].print(c[path[i - 1]][path[i]]);
}
main()
{
read();
del();
getCosts();
calcAns();
printAns();
}