Pagini recente » Cod sursa (job #850716) | Cod sursa (job #1243909) | Cod sursa (job #612038) | Cod sursa (job #1264283) | Cod sursa (job #2520893)
#include <iostream>
#include<cstdio>
#include<fstream>
#include<string>
using namespace std;
ifstream fin("adn.in");
ofstream fout("adn.out");
const int N=18;
int cost[N][N];
string s[N];
int dp[N][1<<N];
char prv[N][1<<N];
const int LENMAX=30005;
const int INF=300000005;
int lsp[LENMAX];
int included[N];
int calculatelps(int id1,int id2){
lsp[0]=lsp[1]=0;
for(int i=2;i<s[id1].size();i++){
int poz=lsp[i-1];
while(s[id1][poz+1]!=s[id1][i] && poz){
poz=lsp[poz];
}
if(s[id1][poz+1]==s[id1][i]){
lsp[i]=poz+1;
}
else
lsp[i]=0;
}
int poz=0;
for(int i=1;i<s[id2].size();i++){
while(s[id1][poz+1]!=s[id2][i] && poz){
poz=lsp[poz];
}
if(s[id1][poz+1]==s[id2][i]){
poz++;
}
else
poz=0;
if(poz==s[id1].size()-1){
included[id2]|=(1<<id1);
}
}
//cout<<s[id2]<<" "<<s[id1]<<" "<<poz<<endl;
return poz;
}
string subs;
int n;
void afis(int id,int mask){
if(prv[id][mask]==-1){
subs=s[id].substr(1);
fout<<subs;
return;
}
int noumask=mask;
for(int i=0;i<n;i++){
if(noumask&(1<<i) && included[id]&(1<<i))
noumask^=(1<<i);
}
afis(prv[id][mask],noumask);
subs=s[id].substr(s[id].size()-cost[prv[id][mask]][id]);
fout<<subs;
}
int main()
{
fin>>n>>ws;
for(int i=0;i<n;i++){
fin>>s[i];
s[i]=" "+s[i];
}
for(int i=0;i<n;i++){
included[i]|=(1<<i);
for(int j=0;j<n;j++){
if(i!=j){
cost[i][j]=s[j].size()-1-calculatelps(j,i);
}
}
}
for(int i=0;i<n;i++){
for(int m=0;m<1<<n;m++){
dp[i][m]=INF;
}
}
for(int i=0;i<n;i++){
dp[i][included[i]]=s[i].size()-1;
prv[i][included[i]]=-1;
}
for(int mask=0;mask<1<<n;mask++){
for(int i=0;i<n;i++){
if(mask & (1<<i) && dp[i][mask]!=INF){
for(int j=0;j<n;j++){
if(!(mask&(1<<j)) && dp[j][mask|included[j]]>dp[i][mask]+cost[i][j]){
dp[j][mask|included[j]]=dp[i][mask]+cost[i][j];
prv[j][mask|included[j]]=i;
}
}
}
}
}
int sol=INF,idsol;
for(int i=0;i<n;i++){
if(sol>dp[i][(1<<n)-1]){
sol=dp[i][(1<<n)-1];
idsol=i;
}
}
afis(idsol,(1<<n)-1);
return 0;
}