Pagini recente » Cod sursa (job #2313035) | Cod sursa (job #58097) | Cod sursa (job #2392988) | Cod sursa (job #3192534) | Cod sursa (job #2313909)
#include<fstream>
#include<cstring>
#define DIM 30005
using namespace std;
int n, i, ii, j, jj, L, x;
int d[(1 << 18) + 2][18], p[DIM], a[20][20], m[20], t[(1 << 18) + 2][18], ok[20];
char s[19][DIM];
ifstream fin("adn.in");
ofstream fout("adn.out");
void solve(int x, int ii){
if(t[x][ii] == 0){
for(int i = 1; i <= m[ii]; i++){
fout<< s[ii][i];
}
return;
}
int y = t[x][ii];
solve(x - (1 << ii), y);
for(int i = a[y][ii] + 1; i <= m[ii]; i++){
fout<< s[ii][i];
}
}
int main(){
fin>> n;
for(i = 0; i < n; i++){
fin>> s[i] + 1;
m[i] = strlen(s[i] + 1);
}
for(ii = 0; ii < n; ii++){
L = 0;
for(i = 2; i <= m[ii]; i++){
while(L != 0 && s[ii][L + 1] != s[ii][i]){
L = p[L];
}
if(s[ii][L + 1] == s[ii][i]){
L++;
}
p[i] = L;
}
for(jj = 0; jj < n; jj++){
L = 0;
for(i = 1; i <= m[jj]; i++){
while(L != 0 && s[ii][L + 1] != s[jj][i]){
L = p[L];
}
if(s[ii][L + 1] == s[jj][i]){
L++;
}
if(L == m[ii] && ii != jj){
ok[ii] = 1;
}
}
a[jj][ii] = L;
}
}
for(ii = 0; ii < (1 << n); ii++){
for(i = 0; i < n; i++){
d[ii][i] = 1000000000;
}
}
for(i = 0; i < n; i++){
d[ (1 << i) ][i] = m[i];
}
for(ii = 2; ii < (1 << n); ii++){
for(i = 0; i < n; i++){
if(d[ii][i] != 1000000000 || ( (ii >> i) & 1) == 0){
continue;
}
for(j = 0; j < n; j++){
if(i != j){
if(d[ii][i] > d[ii - (1 << i)][j] + m[i] - a[j][i]){
d[ii][i] = d[ii - (1 << i)][j] + m[i] - a[j][i];
t[ii][i] = j;
}
}
}
}
}
for(i = 0; i < n; i++){
if(ok[i] == 0){
x += (1 << i);
}
}
ii = 0;
for(i = 1; i < n; i++){
if(d[x][i] < d[x][ii]){
ii = i;
}
}
solve(x, ii);
return 0;
}