C++ Library for Competitive Programming
/*
* @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;
}