levenshtein_distance.cpp

#include<iostream>
#include<cstdlib>
#include<vector>
#include<algorithm>

#define long long long
#define nln '\n'

using namespace std;

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0)->sync_with_stdio(0);
    //freopen("levenshtein_distance.inp", "r", stdin);
    string st1, st2;
    getline(cin, st1, nln);
    getline(cin, st2, nln);
    long n = st1.size(), m = st2.size();
    st1 = '$' + st1;
    st2 = '$' + st2;
    // Dynamic planning
    vector<vector<long>> dp(n+1);
    for (long i = 0; i <= n; ++i)
        dp[i].resize(m+1, 0);
    for (long i = 1; i <= n; ++i)
        dp[i][0] = i;
    for (long j = 1; j <= m; ++j)
        dp[0][j] = j;
    for (long i = 1; i <= n; ++i)
        for (long j = 1; j <= m; ++j)
            dp[i][j] = min(dp[i-1][j-1]+(long)(st1[i] != st2[j]), min(dp[i-1][j], dp[i][j-1])+1);
    cout << dp[n][m] << nln;
    return 0;
}