test/aoj/DPL_1_E/main.test.cpp
Depends on
Code
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_E"
#include <iostream>
#include <string>
#include "Mylib/String/levenshtein_distance.cpp"
namespace hl = haar_lib;
int main() {
std::string s1, s2;
std::cin >> s1 >> s2;
auto ans = hl::levenshtein_distance(s1, s2);
std::cout << ans << std::endl;
return 0;
}
#line 1 "test/aoj/DPL_1_E/main.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_E"
#include <iostream>
#include <string>
#line 2 "Mylib/String/levenshtein_distance.cpp"
#include <algorithm>
#include <vector>
namespace haar_lib {
template <typename Container>
int levenshtein_distance(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 = 0; i <= n; ++i) dp[i][0] = i;
for (int i = 0; i <= m; ++i) dp[0][i] = i;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
dp[i + 1][j + 1] = std::min(dp[i][j + 1] + 1, dp[i + 1][j] + 1);
if (a[i] == b[j]) {
dp[i + 1][j + 1] = std::min(dp[i + 1][j + 1], dp[i][j]);
} else {
dp[i + 1][j + 1] = std::min(dp[i + 1][j + 1], dp[i][j] + 1);
}
}
}
return dp[n][m];
}
} // namespace haar_lib
#line 6 "test/aoj/DPL_1_E/main.test.cpp"
namespace hl = haar_lib;
int main() {
std::string s1, s2;
std::cin >> s1 >> s2;
auto ans = hl::levenshtein_distance(s1, s2);
std::cout << ans << std::endl;
return 0;
}
Back to top page