Levenshtein distance / Edit distance
(Mylib/String/levenshtein_distance.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Link: View error logs on GitHub Actions

Operations

Requirements

Notes

Problems

References

Verified with

• test/aoj/DPL_1_E/main.test.cpp

Code

#pragma once
#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 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

Back to top page