動的計画法/レーベンシュタイン距離
(test/dynamic_programming/levenshtein_distance.test.cpp)

• View this file on GitHub
• Last update: 2023-02-25 01:48:23+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_E

Depends on

• レーベンシュタイン距離 (Levenshtein distance) / 編集距離 (edit distance) (include/emthrm/dynamic_programming/levenshtein_distance.hpp)

Code

/*
 * @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;
}

Back to top page