動的計画法/最長共通部分列
(test/dynamic_programming/longest_common_subsequence.test.cpp)

• View this file on GitHub
• Last update: 2023-02-25 01:48:23+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C

Depends on

• 最長共通部分列 (longest common subsequence) (include/emthrm/dynamic_programming/longest_common_subsequence.hpp)

Code

/*
 * @title 動的計画法/最長共通部分列
 *
 * verification-helper: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C
 */

#include <iostream>
#include <string>

#include "emthrm/dynamic_programming/longest_common_subsequence.hpp"

int main() {
  int q;
  std::cin >> q;
  while (q--) {
    std::string s, t;
    std::cin >> s >> t;
    std::cout << emthrm::longest_common_subsequence(s, t).length() << '\n';
  }
  return 0;
}

#line 1 "test/dynamic_programming/longest_common_subsequence.test.cpp"
/*
 * @title 動的計画法/最長共通部分列
 *
 * verification-helper: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C
 */

#include <iostream>
#include <string>

#line 1 "include/emthrm/dynamic_programming/longest_common_subsequence.hpp"



#include <algorithm>
#include <vector>

namespace emthrm {

template <typename T>
T longest_common_subsequence(const T& a, const T& b) {
  int a_size = a.size(), b_size = b.size();
  std::vector<std::vector<int>> dp(a_size + 1, std::vector<int>(b_size + 1, 0));
  for (int i = 0; i < a_size; ++i) {
    for (int j = 0; j < b_size; ++j) {
      dp[i + 1][j + 1] =
          (a[i] == b[j] ? dp[i][j] + 1 : std::max(dp[i][j + 1], dp[i + 1][j]));
    }
  }
  T res;
  while (a_size > 0 && b_size > 0) {
    if (dp[a_size][b_size] == dp[a_size - 1][b_size]) {
      --a_size;
    } else if (dp[a_size][b_size] == dp[a_size][b_size - 1]) {
      --b_size;
    } else {
      res.push_back(a[--a_size]);
      --b_size;
    }
  }
  std::reverse(res.begin(), res.end());
  return res;
}

}  // namespace emthrm


#line 11 "test/dynamic_programming/longest_common_subsequence.test.cpp"

int main() {
  int q;
  std::cin >> q;
  while (q--) {
    std::string s, t;
    std::cin >> s >> t;
    std::cout << emthrm::longest_common_subsequence(s, t).length() << '\n';
  }
  return 0;
}

Back to top page