test/LCS.test.cpp

• View this file on GitHub
• Last update: 2021-03-21 09:59:09+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_10_C

Depends on

• DP/LCS.cpp

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_10_C"
#include "./../DP/LCS.cpp"
#include <iostream>
#include <string>
using namespace std;

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	int q;
	cin >> q;
	while (q--) {
		string s, t;
		cin >> s >> t;
		cout << LCS(s, t) << '\n';
	}
}

#line 1 "test/LCS.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_10_C"
#line 2 "DP/LCS.cpp"
#include <vector>
#include <string>
#include <algorithm>

int LCS(const std::string& s, const std::string& t) {
	int n = s.size(), m = t.size();
	std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1));
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (s[i] == t[j]) dp[i + 1][j + 1] = std::max(dp[i + 1][j + 1], dp[i][j] + 1);
			dp[i + 1][j + 1] = std::max(dp[i + 1][j + 1], dp[i + 1][j]);
			dp[i + 1][j + 1] = std::max(dp[i + 1][j + 1], dp[i][j + 1]);
		}
	}
	return dp[n][m];
}
#line 3 "test/LCS.test.cpp"
#include <iostream>
#line 5 "test/LCS.test.cpp"
using namespace std;

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	int q;
	cin >> q;
	while (q--) {
		string s, t;
		cin >> s >> t;
		cout << LCS(s, t) << '\n';
	}
}

Back to top page