Longest Common Subsequence
(lib/dp/LCS.hpp)

• View this file on GitHub
• Last update: 2024-05-04 18:06:16+09:00
• Include: #include "lib/dp/LCS.hpp"

Longest Common Subsequence

概要

文字列 $S$ と文字列 $T$ の最長共通部分列を求めます。

計算量

$\mathrm{O}(\lvert S\lvert \lvert T\lvert)$

Verified with

• test/aoj/alds1/alds1_10_c.test.cpp

Code

#pragma once

/**
 * @brief Longest Common Subsequence
 * @docs docs/dp/LCS.md
 */

string LCS(const string &s, const string &t){
    int n = s.size(), m = t.size();
    vector<vector<int>> memo(n + 1, vector<int>(m + 1));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(s[i] == t[j]){
                memo[i + 1][j + 1] = memo[i][j] + 1;
            } else{
                memo[i + 1][j + 1] = max(memo[i][j + 1], memo[i + 1][j]);
            }
        }
    }

    // 復元
    string res = "";
    int i = n - 1, j = m - 1;
    while(0 <= i && 0 <= j){
        if(s[i] == t[j]){
            res += s[i];
            i--; j--;
        } else if(memo[i + 1][j + 1] == memo[i][j + 1]){
            i--;
        } else if(memo[i + 1][j + 1] == memo[i + 1][j]){
            j--;
        }
    }
    reverse(res.begin(), res.end());
    return res;
}

#line 2 "lib/dp/LCS.hpp"

/**
 * @brief Longest Common Subsequence
 * @docs docs/dp/LCS.md
 */

string LCS(const string &s, const string &t){
    int n = s.size(), m = t.size();
    vector<vector<int>> memo(n + 1, vector<int>(m + 1));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(s[i] == t[j]){
                memo[i + 1][j + 1] = memo[i][j] + 1;
            } else{
                memo[i + 1][j + 1] = max(memo[i][j + 1], memo[i + 1][j]);
            }
        }
    }

    // 復元
    string res = "";
    int i = n - 1, j = m - 1;
    while(0 <= i && 0 <= j){
        if(s[i] == t[j]){
            res += s[i];
            i--; j--;
        } else if(memo[i + 1][j + 1] == memo[i][j + 1]){
            i--;
        } else if(memo[i + 1][j + 1] == memo[i + 1][j]){
            j--;
        }
    }
    reverse(res.begin(), res.end());
    return res;
}

Back to top page