src/old/LongestCommonSubsequence.hpp

• View this file on GitHub
• Last update: 2020-04-25 17:53:12+09:00
• Include: #include "src/old/LongestCommonSubsequence.hpp"

Code

// Longest Common Subsequence: O(nm)
vector<vector<int>> LCS(const vector<int>& s, const vector<int>& t) {
    int n = s.size(), m = t.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1));
    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 : max(dp[i][j + 1], dp[i + 1][j]);
        }
    }
    return dp;
}
// メモリ節約
vector<vector<int>> LCS2(const vector<int>& s, const vector<int>& t) {
    int n = s.size(), m = t.size();
    vector<vector<int>> dp(2, vector<int>(m + 1));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            dp[1][j + 1] = s[i] == t[j] ? dp[0][j] + 1 : max(dp[0][j + 1], dp[1][j]);
        }
        swap(dp[0], dp[1]);
    }
    return dp;
}

#line 1 "src/old/LongestCommonSubsequence.hpp"
// Longest Common Subsequence: O(nm)
vector<vector<int>> LCS(const vector<int>& s, const vector<int>& t) {
    int n = s.size(), m = t.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1));
    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 : max(dp[i][j + 1], dp[i + 1][j]);
        }
    }
    return dp;
}
// メモリ節約
vector<vector<int>> LCS2(const vector<int>& s, const vector<int>& t) {
    int n = s.size(), m = t.size();
    vector<vector<int>> dp(2, vector<int>(m + 1));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            dp[1][j + 1] = s[i] == t[j] ? dp[0][j] + 1 : max(dp[0][j + 1], dp[1][j]);
        }
        swap(dp[0], dp[1]);
    }
    return dp;
}

Back to top page