Luzhiled's Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ei1333/library

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

概要

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

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

計算量

Verified with

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