Cod sursa(job #797916)

Utilizator JohnPeterJohn Peter JohnPeter Data 15 octombrie 2012 10:26:00
Problema ADN Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.33 kb
#include<cstdio>
#include<cassert>
#include<vector>
#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

int n, cost[20][20], isin[20];
string t[20];

int cmp(string x, string y){
	return x.size() > y.size();
}

int pr[30010], dp[30010];

void pref(string x, int sz){
	for(int i = 0; i < sz; ++i)
		dp[i] = 0;
	for(int i = 0; i < x.size(); ++i)
		pr[i] = 0;
	
	for(int i = 1; i < x.size(); ++i){
		int p = i;
		do{
			--p;
			p = pr[p];
			if(x[i] == x[p]){
				pr[i] = pr[p] + 1;
				break;
			}
		}while(p != 0);
	}
}

int kmp(string x, string y){
	pref(y, x.size());
	for(int i = 0; i < x.size(); ++i){
		int p = i;
		do{
			--p;
			p = pr[p];
			if(x[i] == y[p]){
				dp[i] = dp[p] + 1;
				break;
			}
		}while(p!= 0);
	}
	return y.size() - dp[x.size() - 1];
}

void read(){
	assert(freopen("adn.in", "r", stdin));
	
	cin >> n;
	
	for(int i = 1; i <= n; ++i)
		cin >> t[i];
	
	sort(t + 1, t + n + 1, cmp);
	
	for(int i = 2; i <= n; ++i){
		for(int j = 1; j < i; ++j)
			if(kmp(t[j], t[i]) == 0){
				for(int k = i; k < n; ++k)
					t[k] = t[k + 1];
				--n;
				--i;
				break;
			}
	}
	
	for(int i = 2; i <= n; ++i)
		for(int j = 1; j < i; ++j){
			cost[j][i] = kmp(t[j], t[i]);
			cost[i][j] = kmp(t[i], t[j]);
		}
		
}

string ans;
int d[19][300000], dad[19][300000];

void solve(){
	int inf = 1000000000;
	for(int i = 1; i <= n; ++i)
		for(int j = 0; j <= 1 << n; ++j)
			d[i][j] = inf;
	
	for(int i = 1; i <= n; ++i)
		d[i][1 << (i - 1)] = 0;

	int lim = 1 << n;
	
	for(int j = 0; j < lim; ++j){
		for(int i = 1; i <= n; ++i){
			for(int k = 1; k <= n; ++k)
				if(j & (1 << (k - 1)));
				else{
					int x = j + (1 << (k - 1));
					if(d[k][x] > d[i][j] + cost[i][k]){
						dad[k][x] = i;
						d[k][x] = d[i][j] + cost[i][k];
					}
				}
		}
	}
	
	int p = inf, pos = 0;
	
	for(int i = 1; i <= n; ++i)
		if(d[i][lim - 1] < p){
			pos = i;
			p = d[i][lim - 1];
		}
	
	int k = pos, r = lim - 1;
	vector<int> lol;
	while(k){
		lol.push_back(k);
		int aux = k;
		k = dad[k][r];
		r = r - (1 << (aux - 1));
	}
	
	for(int i = lol.size() - 1; i >= 0; --i)
		ans += t[lol[i]];
}

void write(){
	assert(freopen("adn.out", "w", stdout));
	
	cout << ans;
}

int main(){
	read();
	solve();
	write();
	
	return 0;
}