test/string/LevenshteinDistance-1.test.cpp

• View this file on GitHub
• Last update: 2023-05-30 04:39:19+09:00
• Problem: https://yukicoder.me/problems/no/225

Depends on

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

Code

#define PROBLEM "https://yukicoder.me/problems/no/225"

#include <vector>
#include <iostream>
#include <string>
using namespace std;
#include "../../lib/50-string/LevenshteinDistance.cpp"

int main() {
    cin.tie(0);ios::sync_with_stdio(false);
    int a; cin >> a >> a;
    string S,T; cin >> S >> T;
    cout << LevenshteinDistance(S,T) << endl;
    return 0;
}

#line 1 "test/string/LevenshteinDistance-1.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/225"

#include <vector>
#include <iostream>
#include <string>
using namespace std;
#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];
}
#line 8 "test/string/LevenshteinDistance-1.test.cpp"

int main() {
    cin.tie(0);ios::sync_with_stdio(false);
    int a; cin >> a >> a;
    string S,T; cin >> S >> T;
    cout << LevenshteinDistance(S,T) << endl;
    return 0;
}

Back to top page