LevenshteinDistance - 編集距離
(lib/50-string/LevenshteinDistance.cpp)

• View this file on GitHub
• Last update: 2023-05-30 04:23:09+09:00

LevenshteinDistance

• 文字列Sを文字列Tに変換するときの編集距離を求める

メソッド

• int LevenshteinDistance(string S, string T,char dummy=’#’)
  • dummyはS,Tに含まれない文字列が良い。
  • SのサイズをN,TのサイズをMとして $O(NM)$

Verified with

• test/string/LevenshteinDistance-1.test.cpp
• test/string/LevenshteinDistance-2.test.cpp

Code

/*
 * @title LevenshteinDistance - 編集距離
 * @docs md/string/LevenshteinDistance.md
 */
int LevenshteinDistance(string S, string T,char dummy='#') {
    int N = S.size();
    int M = T.size();
    S.push_back(dummy);T.push_back(dummy);
    vector<vector<int>> dp(N+2, vector<int>(M+2,N+M));
    dp[0][0]=0;
    for(int i=0;i<=N;++i) {
        for(int j=0;j<=M;++j) {
            //change
            dp[i+1][j+1] = min(dp[i+1][j+1],dp[i][j]+(S[i]!=T[j]));            
            //delete
            dp[i+1][j]   = min(dp[i+1][j],dp[i][j]+1);            
            //insert
            dp[i][j+1]   = min(dp[i][j+1],dp[i][j]+1);            
        }
    }
    return dp[N][M];
}

#line 1 "lib/50-string/LevenshteinDistance.cpp"
/*
 * @title LevenshteinDistance - 編集距離
 * @docs md/string/LevenshteinDistance.md
 */
int LevenshteinDistance(string S, string T,char dummy='#') {
    int N = S.size();
    int M = T.size();
    S.push_back(dummy);T.push_back(dummy);
    vector<vector<int>> dp(N+2, vector<int>(M+2,N+M));
    dp[0][0]=0;
    for(int i=0;i<=N;++i) {
        for(int j=0;j<=M;++j) {
            //change
            dp[i+1][j+1] = min(dp[i+1][j+1],dp[i][j]+(S[i]!=T[j]));            
            //delete
            dp[i+1][j]   = min(dp[i+1][j],dp[i][j]+1);            
            //insert
            dp[i][j+1]   = min(dp[i][j+1],dp[i][j]+1);            
        }
    }
    return dp[N][M];
}

Back to top page