This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ei1333/library
#include "dp/edit-distance.hpp"
レーベルシュタイン距離とも呼ばれる. $2$ つの文字列がどの程度異なっているかを示す距離の一種である.
$1$ 文字の挿入・削除・置換によって, 一方の文字列をもう一方の文字列に変形するのに必要な手順の最小値として定義される.
edit_distance(S, T)
S, T
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]; }