verify/aoj-DPL_1_E-edit_distance.test.cpp

View this file on GitHub
Last update: 2025-07-03 00:41:25+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/1/DPL_1_E

Depends on

Edit Distance（編集距離） (algorithm/String/edit_distance.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/1/DPL_1_E"

#include <iostream>
#include <string>

#include "../algorithm/String/edit_distance.hpp"

int main() {
    std::string s, t;
    std::cin >> s >> t;

    auto ans = algorithm::edit_distance(s, t);
    std::cout << ans << std::endl;
}

#line 1 "verify/aoj-DPL_1_E-edit_distance.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/1/DPL_1_E"

#include <iostream>
#include <string>

#line 1 "algorithm/String/edit_distance.hpp"



/**
 * @brief Edit Distance（編集距離）
 * @docs docs/String/edit_distance.md
 */

#include <algorithm>
#include <vector>

namespace algorithm {

// 2つの配列に対して，編集距離 (Edit Distance) を求める．
// 引数はSTLのシーケンスコンテナであること．O(|S|*|T|).
template <class Sequence>
int edit_distance(const Sequence &s, const Sequence &t) {
    const int n = s.size(), m = t.size();
    // dp[i][j]:=(s[:i]とt[:j]の編集距離).
    std::vector<std::vector<int> > dp(n + 1, std::vector<int>(m + 1, 0));
    for(int i = 1; i <= n; ++i) dp[i][0] = i;
    for(int j = 1; j <= m; ++j) dp[0][j] = j;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            dp[i + 1][j + 1] = std::min({dp[i][j + 1] + 1,
                                         dp[i + 1][j] + 1,
                                         dp[i][j] + (s[i] == t[j] ? 0 : 1)});
        }
    }
    return dp[n][m];
}

}  // namespace algorithm


#line 7 "verify/aoj-DPL_1_E-edit_distance.test.cpp"

int main() {
    std::string s, t;
    std::cin >> s >> t;

    auto ans = algorithm::edit_distance(s, t);
    std::cout << ans << std::endl;
}