Cod sursa(job #2520920)

Utilizator ivan.tudorIvan Tudor ivan.tudor Data 9 ianuarie 2020 21:59:40
Problema ADN Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.16 kb
#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 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);
    }
  }
  return poz;
}
int noumask;
int bit;
void afis(int id,int mask){
  if(prv[id][mask]==-1 || mask==0){
    for(int i=1;i<s[id].size();i++)
      fout<<s[id][i];
    return;
  }
  afis(prv[id][mask],mask^included[id]);
  for(int i=s[id].size()-cost[prv[id][mask]][id];i<s[id].size();i++)
    fout<<s[id][i];
}
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;
}