Longest common subsequence
(Mylib/String/longest_common_subsequence.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00

Operations

• lcs(a[N], b[M])
  • aとbの最長共通部分列の長さを返す。
  • Time complexity $O(NM)$

Requirements

Notes

Problems

References

Verified with

• test/aoj/ALDS1_10_C/main.test.cpp

Code

#pragma once
#include <algorithm>
#include <vector>

namespace haar_lib {
  template <typename Container>
  int lcs(const Container &a, const Container &b) {
    const int n = a.size(), m = b.size();

    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1, 0));
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= m; ++j) {
        dp[i][j] = a[i - 1] == b[j - 1] ? dp[i - 1][j - 1] + 1 : std::max(dp[i - 1][j], dp[i][j - 1]);
      }
    }

    return dp[n][m];
  }
}  // namespace haar_lib

#line 2 "Mylib/String/longest_common_subsequence.cpp"
#include <algorithm>
#include <vector>

namespace haar_lib {
  template <typename Container>
  int lcs(const Container &a, const Container &b) {
    const int n = a.size(), m = b.size();

    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1, 0));
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= m; ++j) {
        dp[i][j] = a[i - 1] == b[j - 1] ? dp[i - 1][j - 1] + 1 : std::max(dp[i - 1][j], dp[i][j - 1]);
      }
    }

    return dp[n][m];
  }
}  // namespace haar_lib

Back to top page