test/edit_distance.test.cpp

• View this file on GitHub
• Last update: 2022-10-23 13:46:28+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_E&lang=ja

Depends on

• dynamic_programming/edit_distance.cpp

Code

#include <bits/stdc++.h>
using namespace std;

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_E&lang=ja"
#include "../dynamic_programming/edit_distance.cpp"

int main() {
    string s, t;
    cin >> s >> t;
    cout << edit_distance(s, t) << '\n';
    return 0;
}

#line 1 "test/edit_distance.test.cpp"
#include <bits/stdc++.h>
using namespace std;

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_E&lang=ja"
#line 3 "dynamic_programming/edit_distance.cpp"
using namespace std;

#line 2 "template/const.hpp"
constexpr int INF        = 1000'000'000;
constexpr long long HINF = 4000'000'000'000'000'000;
constexpr long long MOD  = 998244353;
constexpr double EPS     = 1e-6;
constexpr double PI      = 3.14159265358979;
#line 6 "dynamic_programming/edit_distance.cpp"

// edit_distance
// 文字列s,文字列tの編集距離, すなわち以下の操作をしてsをtに等しくするために必要な操作回数の最小値
// 1. sから文字を一つ取り除く
// 2. sに文字を一つ挿入する
// 3. sの文字を一つ変換する
// 計算量: O(|S||T|)
int edit_distance(string s, string t) {
    int n = (int)s.size(), m = (int)t.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, INF));
    for (int j = 0; j <= m; j++)
        dp[0][j] = j;
    for (int i = 0; i <= n; i++) {
        dp[i][0] = i;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (s[i] == t[j]) dp[i + 1][j + 1] = dp[i][j];
            dp[i + 1][j + 1] = min({dp[i + 1][j + 1], dp[i][j + 1] + 1, dp[i + 1][j] + 1, dp[i][j] + 1});
        }
    }
    return dp[n][m];
}
#line 6 "test/edit_distance.test.cpp"

int main() {
    string s, t;
    cin >> s >> t;
    cout << edit_distance(s, t) << '\n';
    return 0;
}

Back to top page