lcs_algo

namespace lcs_algo {
  using uint64 = unsigned long long;

  constexpr int B = 64;

  std::vector<uint64> bitDP(const std::string& s, const std::string& t, const std::vector<int>& id, int id_cnt) {
    int m = int(t.size());
    int sz = (m + B - 1) / B;
    std::vector bs(id_cnt, std::vector<uint64>(sz));
    for (int i = 0; i < m; ++i) {
      bs[id[t[i]]][i / B] |= 1ULL << (i % B);
    }
    std::vector<uint64> dp(sz);
    for (const char& c : s) {
      const auto& on = bs[id[c]];
      uint64 extra = 1;
      for (int i = 0; i < sz; ++i) {
        uint64 x = on[i] | dp[i];
        uint64 sub = (dp[i] << 1) + extra;
        extra = (x < sub) + (dp[i] >> 63);
        dp[i] = x & (x ^ (x - sub));
      }
      if (m % B != 0) {
        dp[sz - 1] &= (1ULL << (m % B)) - 1;
      }
    }
    return dp;
  }

  int getLcsLength(const std::string& s, const std::string& t) {
    std::vector<int> id(std::numeric_limits<char>::max() + 1, -1);
    int new_id = 0;
    for (const auto& c : s) {
      if (id[c] == -1) {
        id[c] = new_id++;
      }
    }
    for (const auto& c : t) {
      if (id[c] == -1) {
        id[c] = new_id++;
      }
    }
    auto dp = bitDP(s, t, id, new_id);
    int res = 0;
    for (const auto& x : dp) {
      res += __builtin_popcountll(x);
    }
    return res;
  }

  std::string getLcs(const std::string& s, const std::string& t) {
    if (s.empty()) {
      return "";
    }
    std::vector<int> id(std::numeric_limits<char>::max() + 1, -1);
    int new_id = 0;
    for (const auto& c : s) {
      if (id[c] == -1) {
        id[c] = new_id++;
      }
    }
    for (const auto& c : t) {
      if (id[c] == -1) {
        id[c] = new_id++;
      }
    }
    std::string res;
    auto dfs = [&](auto&& dfs, int x, int y, int l, int r) -> void {
      if (y - x == 1) {
        for (int i = l; i < r; ++i) {
          if (s[x] == t[i]) {
            res += s[x];
            break;
          }
        }
        return;
      }
      int m = x + (y - x) / 2;
      auto dp_up = bitDP({s.begin() + x, s.begin() + m}, {t.begin() + l, t.begin() + r}, id, new_id);
      auto dp_down = bitDP({s.rbegin() + s.size() - y, s.rbegin() + s.size() - m}, {t.rbegin() + t.size() - r, t.rbegin() + t.size() - l}, id, new_id);
      int cur_d = 0;
      for (const auto& x : dp_down) {
        cur_d += __builtin_popcountll(x);
      }
      int p = l;
      int max_d = cur_d;
      for (int i = l + 1; i <= r; ++i) {
        cur_d += (dp_up[(i - l - 1) / B] >> ((i - l - 1) % B) & 1);
        cur_d -= (dp_down[(r - i) / B] >> ((r - i) % B) & 1);
        if (cur_d > max_d) {
          max_d = cur_d;
          p = i;
        }
      }
      dfs(dfs, x, m, l, p);
      dfs(dfs, m, y, p, r);
    };
    dfs(dfs, 0, int(s.size()), 0, int(t.size()));
    return res;
  }

  std::string hirschberg(const std::string& s, const std::string& t) {
    if (s.empty()) {
      return "";
    }
    std::string res;
    auto dfs = [&](auto&& dfs, int x, int y, int l, int r) -> void {
      if (y - x == 1) {
        for (int i = l; i < r; ++i) {
          if (s[x] == t[i]) {
            res += s[x];
            break;
          }
        }
        return;
      }
      int m = x + (y - x) / 2;
      std::vector<int> dp_up(r - l + 1);
      for (int row = x; row < m; ++row) {
        auto new_dp = dp_up;
        for (int col = l; col < r; ++col) {
          new_dp[col - l + 1] = std::max(std::max(new_dp[col - l], dp_up[col - l + 1]), dp_up[col - l] + (s[row] == t[col]));
        }
        dp_up = std::move(new_dp);
      }
      std::vector<int> dp_down(r - l + 1);
      for (int row = y - 1; row >= m; --row) {
        auto new_dp = dp_down;
        for (int col = r - 1; col >= l; --col) {
          new_dp[col - l] = std::max(std::max(new_dp[col - l], new_dp[col - l + 1]), dp_down[col - l + 1] + (s[row] == t[col]));
        }
        dp_down = std::move(new_dp);
      }
      int p = -1;
      for (int i = l; i <= r; ++i) {
        if (p == -1 || dp_up[p - l] + dp_down[p - l] < dp_up[i - l] + dp_down[i - l]) {
          p = i;
        }
      }
      dfs(dfs, x, m, l, p);
      dfs(dfs, m, y, p, r);
    };
    dfs(dfs, 0, int(s.size()), 0, int(t.size()));
    return res;
  }
} // namespace lcs_algo