Edit Distance(編集距離) (dp/edit-distance.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-04-27 01:27:28+09:00
• Include: #include "dp/edit-distance.hpp"

概要

レーベルシュタイン距離とも呼ばれる. $2$ つの文字列がどの程度異なっているかを示す距離の一種である.

$1$ 文字の挿入・削除・置換によって, 一方の文字列をもう一方の文字列に変形するのに必要な手順の最小値として定義される.

• edit_distance(S, T): 文字列 S, T の編集距離を返す.

計算量

• $O(nm)$

Verified with

• test/verify/aoj-dpl-1-e.test.cpp

Code

int edit_distance(const string &S, const string &T) {
  const int N = (int)S.size(), M = (int)T.size();
  vector<vector<int> > dp(N + 1, vector<int>(M + 1, N + M));
  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 = 1; i <= N; i++) {
    for (int j = 1; j <= M; j++) {
      dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1);
      dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1);
      dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + (S[i - 1] != T[j - 1]));
    }
  }
  return dp[N][M];
}

#line 1 "dp/edit-distance.hpp"
int edit_distance(const string &S, const string &T) {
  const int N = (int)S.size(), M = (int)T.size();
  vector<vector<int> > dp(N + 1, vector<int>(M + 1, N + M));
  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 = 1; i <= N; i++) {
    for (int j = 1; j <= M; j++) {
      dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1);
      dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1);
      dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + (S[i - 1] != T[j - 1]));
    }
  }
  return dp[N][M];
}

Back to top page