Cod sursa(job #2961221)

Utilizator AdelaCorbeanuAdela Corbeanu AdelaCorbeanu Data 5 ianuarie 2023 23:43:26
Problema ADN Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.01 kb
#include <bits/stdc++.h>

// construieste functia de prefixe pentru sirul s 
void kmp(const std::string &s, std::vector<int> &prefix_function) {
  prefix_function.resize(s.size());
  prefix_function[0] = -1;

  for (int i = 1; i < (int)s.size() ; ++i) {
    prefix_function[i] = prefix_function[i - 1];
    while (prefix_function[i] >= 0 && s[i] != s[prefix_function[i] + 1])
      prefix_function[i] = prefix_function[prefix_function[i]];

    if (s[i] == s[prefix_function[i] + 1])
      ++prefix_function[i];
  }
}

// verifica daca un sir este subsecventa stringului s
bool check_subsequence(const std::string &s, const std::string &subsequence, const std::vector<int> &prefix_function) {
  int i = -1;
  for (auto ch : s) {
    while (i >= 0 && subsequence[i + 1] != ch)
      i = prefix_function[i];

    if (ch == subsequence[i + 1])
      ++i;

    if (i + 1 == (int)subsequence.size())
      return true;
  }

  return false;
}

// calculeaza lungimea comuna a prefixului sirului din dreapta si a sufixului sirului din stanga
int compute_common_length(const std::string &left_s, const std::string &right_s, const std::vector<int> &prefix_function) {
  int i = -1;
  for (auto ch : left_s) {
    while (i >= 0 && right_s[i + 1] != ch)
      i = prefix_function[i];

    if (ch == right_s[i + 1])
      ++i;
  }

  return i + 1;
}

int main() {
  std::ifstream fin("adn.in");
  std::ofstream fout("adn.out");

  // citim stringurile
  int n;
  fin >> n;
  std::vector<std::string> adn_sequences;
  for (int i = 1; i <= n ; ++i) {
    adn_sequences.emplace_back();
    fin >> adn_sequences.back();
  }

  // pentru fiecare secventa adn, aplicam algoritmul kmp pentru a obtine
  // functia de prefixe
  std::vector<std::vector<int>> prefix_functions;
  for (auto &adn_sequence : adn_sequences) {
    prefix_functions.emplace_back();
    kmp(adn_sequence, prefix_functions.back());
  }

  // parcurgem toate secventele adn.
  // daca o secventa adn este subsecventa alteia, o eliminam din sir
  for (int i = 0; i < n ; ++i) {
    for (int j = 0; j < n ; ++j) {
      if (j == i)
        continue;

      if (check_subsequence(adn_sequences[i], adn_sequences[j], prefix_functions[j])) {
        --n;
        for (int t = j; t < n ; ++t)
          adn_sequences[t] = adn_sequences[t + 1];
        adn_sequences.pop_back();

         if (j < i)
           --i;

         --j;
      }
    }
  }

  // calculam pentru fiecare doua secvente adn, care este lungimea pe care o
  // 'salvam' daca am construi un sir care sa contina ambele siruri, unul
  // ca prefix, iar celalalt ca sufix
  // de exemplu pentru sirurile "aaa"" si "abb" am obtine sirul aaabb,
  // deci lungimea "salvata" este 1, deorece din doua stringuri de lungime 3,
  // am obtinut un sir de lungime 5
  std::vector<std::vector<int>> common_length(n, std::vector <int>(n));
  for (int i = 0; i < n ; ++i) {
    for (int j = 0; j < n ; ++j) {
      if (i == j)
        continue;
      common_length[i][j] = compute_common_length(adn_sequences[i], adn_sequences[j], prefix_functions[i]);
    }
  }

  fout << "meow" << std::endl;

  return 0;

  // calculam dinamica dp(mask, i) = costul minim sa alegem secventele din masca,
  // iar ultima secventa aleasa este i

  std::vector<std::vector<int>> dp(1 << n, std::vector<int>(n, 1e9));
  for (int i = 0; i < n ; ++i)
    dp[1 << i][i] = adn_sequences[i].size();

  int max_mask = (1 << n) - 1;
  for (int mask = 1; mask <= max_mask ; ++mask) {
    for (int i = 0; i < n ; ++i) {
      // daca secventa i nu apare in masca, nu poate sa fie ultima secventa aleasa
      if (!((1 << i) & mask))
        continue;
      for (int j = 0; j < n ; ++j) {
        // daca secventa j apare in masca, nu putem sa o alegem din nou
        if ((1 << j) & mask)
          continue;

        dp[mask | (1 << j)][j] = std::min(dp[mask | (1 << j)][j], dp[mask][i] - common_length[i][j] + (int)adn_sequences[j].size());
      }
    }
  }

  // aflam care este ultima secventa si incercam sa reconstruim sirul
  int mn = 1e9, last_sequence = 0;
  for (int i = 0; i < n ; ++i) {
    if (dp[max_mask][i] < mn) {
      mn = dp[max_mask][i];
      last_sequence = i;
    }
  }

  int mask = max_mask;
  std::string answer;

  // cum construim sirul de la ultimul la primul sir, trebuie sa inversam sirurile pe parcurs fiecare sir
  reverse(adn_sequences[last_sequence].begin(), adn_sequences[last_sequence].end());
  answer += adn_sequences[last_sequence];
  mask = mask ^ (1 << last_sequence);
  while (mask > 0) {
    int new_sequence = 0;

    mn = 1e9;
    for (int i = 0; i < n ; ++i) {
      if (((1 << i) & mask) && dp[mask][i] < mn) {
        mn = dp[mask][i];
        new_sequence = i;
      }
    }

    for (int i = 0; i < common_length[new_sequence][last_sequence] ; ++i)
      adn_sequences[new_sequence].pop_back();
    std::reverse(adn_sequences[new_sequence].begin(), adn_sequences[new_sequence].end());

    answer += adn_sequences[new_sequence];
    last_sequence = new_sequence;
    mask = mask ^ (1 << last_sequence);
  }

  std::reverse(answer.begin(), answer.end());
  fout << answer << std::endl;

  return 0;
}