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

• View this file on GitHub
• Last update: 2025-07-03 00:41:25+09:00
• Include: #include "algorithm/String/longest_common_subsequence.hpp"

概要

配列 $S, T$ に対し，最長共通部分列 (LCS: Longest Common Subsequence) を求める． 最長共通部分列とは，2つの配列において，双方に現れる部分列の中で最長のものを指す．

アルゴリズムの計算量は $\mathcal{O}(\lvert S \rvert \lvert T \rvert)$ となる．

参考文献

1. 秋葉 拓哉, 岩田 陽一, 北川 宜稔. “2-3 値を覚えて再利用 ‘動的計画法’”. プログラミングコンテストチャレンジブック. 第2版, マイナビ出版, 2012, p.56-57.

問題

• “F - LCS”. Educational DP Contest / DP まとめコンテスト. AtCoder. https://atcoder.jp/contests/dp/tasks/dp_f.

Verified with

• verify/aoj-ALDS1_10_C-longest_common_subsequence.test.cpp

Code

#ifndef ALGORITHM_LONGEST_COMMON_SUBSEQUENCE_HPP
#define ALGORITHM_LONGEST_COMMON_SUBSEQUENCE_HPP 1

/**
 * @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

#endif

#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

Back to top page