最長共通部分列 (longest common subsequence)
(include/emthrm/dynamic_programming/longest_common_subsequence.hpp)

• View this file on GitHub
• Last update: 2022-12-15 22:18:37+09:00
• Include: #include "emthrm/dynamic_programming/longest_common_subsequence.hpp"

2列に対して双方に現れる部分列の内、最長のものである。

時間計算量

$O(NM)$

仕様

名前	戻り値
template <typename T> T longest_common_subsequence(const T& a, const T& b);	$A$ と $B$ の最長共通部分列

参考文献

• Robert A. Wagner and Michael J. Fischer: The String-to-String Correction Problem, Journal of the ACM, Vol. 21, No. 1, pp. 168–173 (1974). https://doi.org/10.1145/321796.321811
• https://qiita.com/drken/items/03c7db44ccd27820ea0d

TODO

• https://judge.yosupo.jp/problem/prefix_substring_lcs
• https://github.com/yosupo06/library-checker-problems/issues/732
• 高速化
  • http://www.prefield.com/algorithm/dp/lcs_hs.html

Submissons

https://atcoder.jp/contests/dp/submissions/9236673

Verified with

• 動的計画法/最長共通部分列 (test/dynamic_programming/longest_common_subsequence.test.cpp)

Code

#ifndef EMTHRM_DYNAMIC_PROGRAMMING_LONGEST_COMMON_SUBSEQUENCE_HPP_
#define EMTHRM_DYNAMIC_PROGRAMMING_LONGEST_COMMON_SUBSEQUENCE_HPP_

#include <algorithm>
#include <vector>

namespace emthrm {

template <typename T>
T longest_common_subsequence(const T& a, const T& b) {
  int a_size = a.size(), b_size = b.size();
  std::vector<std::vector<int>> dp(a_size + 1, std::vector<int>(b_size + 1, 0));
  for (int i = 0; i < a_size; ++i) {
    for (int j = 0; j < b_size; ++j) {
      dp[i + 1][j + 1] =
          (a[i] == b[j] ? dp[i][j] + 1 : std::max(dp[i][j + 1], dp[i + 1][j]));
    }
  }
  T res;
  while (a_size > 0 && b_size > 0) {
    if (dp[a_size][b_size] == dp[a_size - 1][b_size]) {
      --a_size;
    } else if (dp[a_size][b_size] == dp[a_size][b_size - 1]) {
      --b_size;
    } else {
      res.push_back(a[--a_size]);
      --b_size;
    }
  }
  std::reverse(res.begin(), res.end());
  return res;
}

}  // namespace emthrm

#endif  // EMTHRM_DYNAMIC_PROGRAMMING_LONGEST_COMMON_SUBSEQUENCE_HPP_

#line 1 "include/emthrm/dynamic_programming/longest_common_subsequence.hpp"



#include <algorithm>
#include <vector>

namespace emthrm {

template <typename T>
T longest_common_subsequence(const T& a, const T& b) {
  int a_size = a.size(), b_size = b.size();
  std::vector<std::vector<int>> dp(a_size + 1, std::vector<int>(b_size + 1, 0));
  for (int i = 0; i < a_size; ++i) {
    for (int j = 0; j < b_size; ++j) {
      dp[i + 1][j + 1] =
          (a[i] == b[j] ? dp[i][j] + 1 : std::max(dp[i][j + 1], dp[i + 1][j]));
    }
  }
  T res;
  while (a_size > 0 && b_size > 0) {
    if (dp[a_size][b_size] == dp[a_size - 1][b_size]) {
      --a_size;
    } else if (dp[a_size][b_size] == dp[a_size][b_size - 1]) {
      --b_size;
    } else {
      res.push_back(a[--a_size]);
      --b_size;
    }
  }
  std::reverse(res.begin(), res.end());
  return res;
}

}  // namespace emthrm

Back to top page