verify/dp/longest_common_subsequence.test.cpp

• View this file on GitHub
• Last update: 2025-01-24 21:06:48+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C

Depends on

• Longest Common Subsequence (最長共通部分列) (dp/longest_common_subsequence.hpp)

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C"

#include <iostream>
#include "dp/longest_common_subsequence.hpp"

int main() {
    int N;
    std::cin >> N;
    for (int i = 0; i < N; i++) {
        std::string s, t;
        std::cin >> s >> t;
        std::cout << longest_common_subsequence(s, t).size() << '\n';
    }
    return 0;
}

#line 1 "verify/dp/longest_common_subsequence.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C"

#include <iostream>
#line 2 "dp/longest_common_subsequence.hpp"

#include <vector>
#include <string>
#include <algorithm>

template <class T> std::vector<T> longest_common_subsequence(std::vector<T>& a, std::vector<T>& b) {
    const int n = (int)(a.size()), m = (int)(b.size());
    constexpr int e = -1000000000;  // -INF
    std::vector dp(n + 1, std::vector<int>(m + 1, e));
    std::vector pd(n + 1, std::vector<int>(m + 1, -1));
    // initialize
    for (int i = 0; i < n + 1; i++) dp[i][0] = 0;
    for (int j = 0; j < m + 1; j++) dp[0][j] = 0;
    // dp
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i] == b[j]) {
                if (dp[i + 1][j + 1] < dp[i][j] + 1) {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                    pd[i + 1][j + 1] = 0;
                }
            } else {
                if (dp[i + 1][j + 1] < dp[i + 1][j]) {
                    dp[i + 1][j + 1] = dp[i + 1][j];
                    pd[i + 1][j + 1] = 1;
                }
                if (dp[i + 1][j + 1] < dp[i][j + 1]) {
                    dp[i + 1][j + 1] = dp[i][j + 1];
                    pd[i + 1][j + 1] = 2;
                }
            }
        }
    }
    // 復元
    std::vector<T> res;
    res.reserve(dp[n][m]);
    for (int i = n, j = m; pd[i][j] != -1;) {
        if (pd[i][j] == 0) {
            i--, j--;
            res.push_back(a[i]);
        } else if (pd[i][j] == 1) {
            j--;
        } else {
            // pd[i][j] == 2
            i--;
        }
    }
    std::reverse(res.begin(), res.end());
    return res;
}

std::string longest_common_subsequence(std::string& s, std::string& t) {
    const int n = (int)(s.size()), m = (int)(t.size());
    std::vector<int> a(n), b(m);
    for (int i = 0; i < n; i++) a[i] = s[i];
    for (int j = 0; j < m; j++) b[j] = t[j];
    auto lcs = longest_common_subsequence(a, b);
    const int k = (int)(lcs.size());
    std::string res;
    res.reserve(k);
    for (int i = 0; i < k; i++) res += lcs[i];
    return res;
}
#line 5 "verify/dp/longest_common_subsequence.test.cpp"

int main() {
    int N;
    std::cin >> N;
    for (int i = 0; i < N; i++) {
        std::string s, t;
        std::cin >> s >> t;
        std::cout << longest_common_subsequence(s, t).size() << '\n';
    }
    return 0;
}

Back to top page