Cod sursa(job #813343)

Utilizator SCBbestofSocaciu-Cumpanasu Bogdan SCBbestof Data 15 noiembrie 2012 11:26:27
Problema ADN Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.76 kb
#include<cstdio>
#include<cassert>
#include<string>
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int pi[30005];

void prefix(string &x){
  pi[1] = 0;
  for(int i = 2; i < x.size(); ++i){
    int p = i - 1;
    pi[i] = 0;

    do{
      p = pi[p];

      if(x[i] == x[p + 1]){
        pi[i] = p + 1;
        break;
      }

    }while(p);

  }

}

int mpref[30005];

int kmp_comp(string &x, string &y){
  prefix(y);

  for(int i = 1; i < x.size(); ++i)
    mpref[i] = 0;

  for(int i = 1; i < x.size(); ++i){
    int p = mpref[i - 1];

    if(x[i] == y[p + 1])
      mpref[i] = p + 1;
    else
      do{
        p = pi[p];

        if(x[i] == y[p + 1]){
          mpref[i] = p + 1;
          break;
        }

      }while(p);

    if(mpref[i] == y.size() - 1)
      return 0;
  }

  return y.size() - 1 - mpref[x.size() - 1];
}

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

int n, tab[22][22];
string giv[22];

void read(){
  assert(freopen("adn.in", "r", stdin));

  cin >> n;

  for(int i = 1; i <= n; ++i){
    string aux;
    cin >> aux;
    giv[i].push_back('#');
    giv[i] = giv[i] + aux;
  }

  sort(giv + 1, giv + n + 1, cmp);

  for(int i = 2; i <= n; ++i){
    for(int j = 1; j < i; ++j)
      if(kmp_comp(giv[j], giv[i]) == 0)
        goto label;

    continue;

    label:for(int j = i; j < n; ++j)
      giv[j] = giv[j + 1];

    --i;
    --n;
  }

  for(int i = 1; i <= n; ++i)
    for(int j = 1; j <= n; ++j)
      tab[i][j] = kmp_comp(giv[i], giv[j]);
}

int dp[22][400005], dad[22][400005];
string ans;

void solve(){
  int lim = 1 << n;

  for(int i = 1; i <= n; ++i)
    for(int j = 0; j < lim; ++j)
      dp[i][j] = 1000000000;

  for(int i = 1; i <= n; ++i)
    dp[i][1 << (i - 1)] = giv[i].size() - 1;

  for(int i = 1; i < lim; ++i)
    for(int j = 1; j <= n; ++j)
      for(int k = 1; k <= n; ++k)
        if((1 << (k - 1)) & i);
        else if(dp[j][i] + tab[j][k] < dp[k][i + (1 << (k - 1))]){
          dp[k][i + (1 << (k - 1))] = dp[j][i] + tab[j][k];
          dad[k][i + (1 << (k - 1))] = j;
        }

  vector<int> rec;
  int men = 1000000000, ind = 0;

  for(int i = 1; i <= n; ++i)
    if(dp[i][lim - 1] < men){
      ind = i;
      men = dp[i][lim - 1];
    }

  lim = (1 << n) - 1;
  while(ind){
    rec.push_back(ind);
    int aux = lim;
    lim = lim - (1 << (ind - 1));
    ind = dad[ind][aux];
  }

  for(int i = 1; i < giv[rec[rec.size() - 1]].size(); ++i)
    ans.push_back(giv[rec[rec.size() - 1]][i]);

  for(int i = rec.size() - 2; i >= 0; --i){
    int in = giv[rec[i]].size() - tab[rec[i + 1]][rec[i]];

    for(int j = in; j < giv[rec[i]].size(); ++j)
      ans.push_back(giv[rec[i]][j]);
  }
}

void write(){
  assert(freopen("adn.out", "w", stdout));

  cout << ans;
}

int main(){
  read();
  solve();
  write();

  return 0;
}