This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ningenMe/compro-library
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C" #include <vector> #include <iostream> #include <string> #include <algorithm> using namespace std; #include "../../lib/50-string/LongestCommonSubsequence.cpp" int main() { cin.tie(0);ios::sync_with_stdio(false); int Q; cin >> Q; while(Q--) { string S,T; cin >> S >> T; cout << LongestCommonSubsequence(S,T).size() << endl; } return 0; }
#line 1 "test/string/LongestCommonSubsequence.test.cpp" #define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C" #include <vector> #include <iostream> #include <string> #include <algorithm> using namespace std; #line 1 "lib/50-string/LongestCommonSubsequence.cpp" /* * @title LongestCommonSubsequence - LCS * @docs md/string/LongestCommonSubsequence.md */ string LongestCommonSubsequence(const string& S, const string& T){ int N = S.size(), M = T.size(); vector<int> dp((N+1)*(M+1),0); for(size_t i = 0; i < N; i++) { for(size_t j = 0; j < M; j++) { dp[(i+1)*(M+1)+j+1] = (S[i] == T[j] ? dp[i*(M+1)+j] + 1 : max(dp[i*(M+1)+j + 1],dp[(i+1)*(M+1)+j]) ); } } int a=N,b=M; string res = ""; while(dp[a*(M+1)+b]>0) { if(S[a-1]==T[b-1]) res.push_back(S[a-1]),a--,b--; else (dp[(a-1)*(M+1)+b]>dp[a*(M+1)+b-1]?a:b)--; } reverse(res.begin(),res.end()); return res; } #line 9 "test/string/LongestCommonSubsequence.test.cpp" int main() { cin.tie(0);ios::sync_with_stdio(false); int Q; cin >> Q; while(Q--) { string S,T; cin >> S >> T; cout << LongestCommonSubsequence(S,T).size() << endl; } return 0; }