dynamic_programming/longest_common_sequence.cpp

• View this file on GitHub
• Last update: 2022-08-28 12:10:16+09:00

Verified with

• test/longest_common_sequence.test.cpp

Code

#pragma once
#include <bits/stdc++.h>
using namespace std;

struct LongestCommonSequence {
    int n, m;
    string s, t, ret;
    vector<vector<int>> dp;

    LongestCommonSequence(string s, string t) : s(s), t(t) {
        n = (int)s.size();
        m = (int)t.size();
        dp.assign(n + 1, vector<int>(m + 1, 0));
    }

    // solve
    // 最長共通部分列問題を解いてその長さを返す。
    // 計算量: O(nm)
    int solve() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (s[i] == t[j]) {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                } else {
                    dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
                }
            }
        }
        return dp[n][m];
    }

    // restore_common_string
    // 最長共通部分列(文字列)を返す
    // 計算量: O(l),lは最長共通部分列の長さ
    string restore_common_string() {
        vector<char> ret;
        int ni = n, nj = m;
        while (ni != 0 && nj != 0) {
            if (s[ni - 1] == t[nj - 1]) {
                ret.push_back(s[ni - 1]);
                ni--;
                nj--;
            } else {
                if (dp[ni][nj] == dp[ni - 1][nj])
                    ni--;
                else
                    nj--;
            }
        }
        reverse(ret.begin(), ret.end());
        string ans = "";
        for (auto &c : ret)
            ans += c;
        return ans;
    }
};

#line 2 "dynamic_programming/longest_common_sequence.cpp"
#include <bits/stdc++.h>
using namespace std;

struct LongestCommonSequence {
    int n, m;
    string s, t, ret;
    vector<vector<int>> dp;

    LongestCommonSequence(string s, string t) : s(s), t(t) {
        n = (int)s.size();
        m = (int)t.size();
        dp.assign(n + 1, vector<int>(m + 1, 0));
    }

    // solve
    // 最長共通部分列問題を解いてその長さを返す。
    // 計算量: O(nm)
    int solve() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (s[i] == t[j]) {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                } else {
                    dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
                }
            }
        }
        return dp[n][m];
    }

    // restore_common_string
    // 最長共通部分列(文字列)を返す
    // 計算量: O(l),lは最長共通部分列の長さ
    string restore_common_string() {
        vector<char> ret;
        int ni = n, nj = m;
        while (ni != 0 && nj != 0) {
            if (s[ni - 1] == t[nj - 1]) {
                ret.push_back(s[ni - 1]);
                ni--;
                nj--;
            } else {
                if (dp[ni][nj] == dp[ni - 1][nj])
                    ni--;
                else
                    nj--;
            }
        }
        reverse(ret.begin(), ret.end());
        string ans = "";
        for (auto &c : ret)
            ans += c;
        return ans;
    }
};

Back to top page