C++ Library for Competitive Programming
/*
* @title 動的計画法/レーベンシュタイン距離
*
* verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_E
*/
#include <iostream>
#include <string>
#include "emthrm/dynamic_programming/levenshtein_distance.hpp"
int main() {
std::string s1, s2;
std::cin >> s1 >> s2;
std::cout << emthrm::levenshtein_distance(s1, s2) << '\n';
return 0;
}
#line 1 "test/dynamic_programming/levenshtein_distance.test.cpp"
/*
* @title 動的計画法/レーベンシュタイン距離
*
* verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_E
*/
#include <iostream>
#include <string>
#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
#line 11 "test/dynamic_programming/levenshtein_distance.test.cpp"
int main() {
std::string s1, s2;
std::cin >> s1 >> s2;
std::cout << emthrm::levenshtein_distance(s1, s2) << '\n';
return 0;
}