C++ Library for Competitive Programming
#include "emthrm/dynamic_programming/levenshtein_distance.hpp"
任意の文字を削除・挿入・置換することによって、二つの文字列を一致させるために必要な操作回数の最小値である。
$O(NM)$
名前 | 戻り値 |
---|---|
template <typename T> int levenshtein_distance(const T& a, const T& b);
|
$A$ と $B$ のレーベンシュタイン距離 |
https://onlinejudge.u-aizu.ac.jp/solutions/problem/DPL_1_E/review/4112291/emthrm/C++14
#ifndef EMTHRM_DYNAMIC_PROGRAMMING_LEVENSHTEIN_DISTANCE_HPP_
#define EMTHRM_DYNAMIC_PROGRAMMING_LEVENSHTEIN_DISTANCE_HPP_
#include <algorithm>
#include <numeric>
#include <vector>
namespace emthrm {
template <typename T>
int levenshtein_distance(const T& a, const T& b) {
const int n = a.size(), m = b.size();
std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1));
for (int i = n; i >= 1; --i) {
dp[i][0] = i;
}
std::iota(dp[0].begin(), dp[0].end(), 0);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
dp[i][j] = std::min({dp[i - 1][j] + 1,
dp[i][j - 1] + 1,
dp[i - 1][j - 1] + (a[i - 1] != b[j - 1])});
}
}
return dp[n][m];
}
} // namespace emthrm
#endif // EMTHRM_DYNAMIC_PROGRAMMING_LEVENSHTEIN_DISTANCE_HPP_
#line 1 "include/emthrm/dynamic_programming/levenshtein_distance.hpp"
#include <algorithm>
#include <numeric>
#include <vector>
namespace emthrm {
template <typename T>
int levenshtein_distance(const T& a, const T& b) {
const int n = a.size(), m = b.size();
std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1));
for (int i = n; i >= 1; --i) {
dp[i][0] = i;
}
std::iota(dp[0].begin(), dp[0].end(), 0);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
dp[i][j] = std::min({dp[i - 1][j] + 1,
dp[i][j - 1] + 1,
dp[i - 1][j - 1] + (a[i - 1] != b[j - 1])});
}
}
return dp[n][m];
}
} // namespace emthrm