verify/aoj-ALDS1_10_C-longest_common_subsequence.test.cpp

• View this file on GitHub
• Last update: 2025-07-03 00:41:25+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/10/ALDS1_10_C

Depends on

• Longest Common Subsequence（最長共通部分列） (algorithm/String/longest_common_subsequence.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/10/ALDS1_10_C"

#include <iostream>
#include <string>

#include "../algorithm/String/longest_common_subsequence.hpp"

int main() {
    int q;
    std::cin >> q;

    while(q--) {
        std::string x, y;
        std::cin >> x >> y;

        auto ans = algorithm::lcs(x, y).size();
        std::cout << ans << "\n";
    }
}

#line 1 "verify/aoj-ALDS1_10_C-longest_common_subsequence.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/10/ALDS1_10_C"

#include <iostream>
#include <string>

#line 1 "algorithm/String/longest_common_subsequence.hpp"



/**
 * @brief Longest Common Subsequence（最長共通部分列）
 * @docs docs/String/longest_common_subsequence.md
 */

#include <algorithm>
#include <vector>

namespace algorithm {

// 2つの配列に対して，最長共通部分列 (LCS: Longest Common Subsequence) を求める．
// 引数はSTLのシーケンスコンテナであること．O(|S|*|T|).
template <class Sequence>
Sequence lcs(const Sequence &s, const Sequence &t) {
    const int n = s.size(), m = t.size();
    // dp[i][j]:=(s[:i]とt[:j]のLCSの長さ).
    std::vector<std::vector<int> > dp(n + 1, std::vector<int>(m + 1, 0));
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            dp[i + 1][j + 1] = (s[i] == t[j] ? dp[i][j] + 1 : std::max(dp[i][j + 1], dp[i + 1][j]));
        }
    }
    Sequence sub(dp[n][m], 0);  // sub[]:=(配列s, tのLCS).
    int i = n - 1, j = m - 1, k = dp[n][m] - 1;
    while(k >= 0) {
        if(s[i] == t[j]) {
            sub[k] = s[i];
            i--, j--, k--;
        } else if(dp[i + 1][j + 1] == dp[i][j + 1]) {
            i--;
        } else {
            j--;
        }
    }
    return sub;
}

}  // namespace algorithm


#line 7 "verify/aoj-ALDS1_10_C-longest_common_subsequence.test.cpp"

int main() {
    int q;
    std::cin >> q;

    while(q--) {
        std::string x, y;
        std::cin >> x >> y;

        auto ans = algorithm::lcs(x, y).size();
        std::cout << ans << "\n";
    }
}

Back to top page