Cod sursa(job #1067591)

Utilizator vlad_DVlad Dumitriu vlad_D Data 27 decembrie 2013 07:40:16
Problema ADN Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.22 kb
#include <cstdio>
#include <iostream>
#include <string.h>

using namespace std;

int N;
char adn[19][30007];
int F[19][30007];
int M[19];

void build_failure() {
  for (int k = 0; k < N; ++k) {
    int* FF = F[k];
    char* pat = adn[k];
    FF[0] = FF[1] = 0;
    for (int i = 2; i <= M[k]; ++i) {
      FF[i] = 0;
      int j = FF[i-1];
      while (j) {
        if (pat[j] == pat[i-1]) {
          FF[i] = j + 1; break;
        }
        j = FF[j];
      }
    }
  }
}
int hash_kmp[20][20];
int kmp(int k1, int k2) {
  if (hash_kmp[k1][k2]) return hash_kmp[k1][k2] - 1;
  // k1 ... k2
  int& best = hash_kmp[k1][k2];
  int i = 0, j = 0;
  char* text = adn[k1];
  char* pat = adn[k2];
  while (1) {
    if (i == M[k1]) break; 
    if (text[i] == pat[j]) {
      ++i; ++j;
      if (j > best && i == M[k1]) best = j;
      if (j == M[k2]) { best = M[k2] + 1; return best - 1;}
    } else {
      if (j > 0) j = F[k2][j];
      else ++i;
    }
  }
  best++;
  return best - 1;
}

int dp[1<<18][18];
int go(int mask, int p) {
  if (mask + 1 == (1<<N)) return 0;
  if (dp[mask][p]) return dp[mask][p];
  int& ret = dp[mask][p];
  ret = 30000 * N;
  for (int i = 0; i < N; ++i) if (!(mask & (1 << i))) {
    int now = M[i] - kmp(p, i) + go(mask | (1<<i), i);
    if (now < ret) ret = now;
  }
  return ret;
}

int main() {
  freopen("adn.in", "r", stdin);
  freopen("adn.out", "w", stdout);
  scanf("%d", &N);
  for (int i = 0; i < N; ++i) {
    scanf("%s", &adn[i]);
    M[i] = strlen(adn[i]);
  }
  build_failure();
  int best = 30000 * N + 1;
  int mask = 0;
  for (int i = 0; i < N; ++i)
    for (int j = i + 1; j < N; ++j) if (i != j) if (kmp(i, j) == M[j]) mask |= (1 << j);
  int last_i = 0;
  for (int i = 0; i < N; ++i) if (!(mask & (1 << i))) {
    int now = go(mask | (1<<i), i) + M[i];
    if (now < best) best = now, last_i = i;
  }
  printf("%s", adn[last_i]);
  best -= M[last_i]; mask |= (1<<last_i);
  while (mask + 1 != (1<<N)) {
    for (int i = 0; i < N; ++i) if (!(mask & (1<<i))) {
      int now = go(mask | (1<<i), i) + M[i] - kmp(last_i, i);
      if (now == best) {
        best -= M[i] - kmp(last_i, i);
        printf("%s", adn[i] + kmp(last_i, i));
        last_i = i; mask |= (1<<i);
        break;
      }
    }
  }
  printf("\n");
  return 0;
}