Appearance
LCS（最長共通部分列）
2つの文字列から、順序を保って文字を取り出したときの最長共通部分列を求める典型問題。
イメージ
例えば、
S = "abcde"T = "ace"
共通部分列の1つは "ace" で、LCSの長さは 3。
部分列なので、文字が連続している必要はない。
解法
動的計画法（DP）を使う。
dp[i][j] を、S の先頭 i 文字と T の先頭 j 文字のLCSの長さとする。
- 末尾の文字が一致：
dp[i][j] = dp[i-1][j-1] + 1 - 一致しない：
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
計算量
| 実装 | 時間 | 空間 |
|---|---|---|
| 長さのみ | O(NM) | O(M) |
| 復元あり | O(NM) | O(NM) |
実装
cpp
#pragma once
#include <algorithm>
#include <string>
#include <vector>
// LCS（最長共通部分列）の長さ
// 時間 O(NM)、空間 O(M)
int lcs_length(const std::string& s, const std::string& t) {
int n = s.size(), m = t.size();
std::vector<int> dp(m + 1, 0);
for (int i = 0; i < n; i++) {
int prev = 0;
for (int j = 0; j < m; j++) {
int tmp = dp[j + 1];
if (s[i] == t[j]) dp[j + 1] = prev + 1;
else dp[j + 1] = std::max(dp[j + 1], dp[j]);
prev = tmp;
}
}
return dp[m];
}cpp
#pragma once
#include <algorithm>
#include <string>
#include <vector>
// LCSの1つを復元する
// 時間 O(NM)、空間 O(NM)
std::string lcs_restore(const std::string& s, const std::string& t) {
int n = s.size(), m = t.size();
std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1));
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] = std::max(dp[i][j + 1], dp[i + 1][j]);
}
}
std::string res;
int i = n, j = m;
while (i > 0 && j > 0) {
if (s[i - 1] == t[j - 1]) {
res += s[i - 1];
i--;
j--;
} else if (dp[i - 1][j] >= dp[i][j - 1]) i--;
else j--;
}
std::reverse(res.begin(), res.end());
return res;
}使用例
長さのみ
cpp
cout << lcs_length("abcde", "ace") << '\n'; // 3復元あり
cpp
string res = lcs_restore("abcde", "ace");
cout << res << '\n'; // ace注意点
- 部分列は連続している必要がない。
- 部分文字列（Substring）とは異なる。
- LCSが複数存在する場合、復元結果は一意とは限らない。
- 長さだけ必要なら1次元DPでメモリを削減できる。
- N、Mが大きい場合は O(NM) の計算量に注意する。
関連
- LIS（最長増加部分列）
- 編集距離
- DP復元