string/edit_distance.hpp

View this file on GitHub
Last update: 2022-10-21 16:42:45+09:00
Include: #include "string/edit_distance.hpp"

Verified with

test/yukicoder/1818.test.cpp

Code

template <typename STRING>
int edit_distance(STRING& S, STRING& T) {
  int N = len(S), M = len(T);
  vc<int> dp(M + 1, 1 << 30);
  dp[0] = 0;
  FOR(i, N + 1) {
    vc<int> newdp(M + 1, 1 << 30);
    FOR(j, M + 1) {
      if (i < N) chmin(newdp[j], dp[j] + 1);
      if (j < M) chmin(dp[j + 1], dp[j] + 1);
      if (i < N && j < M) chmin(newdp[j + 1], dp[j] + 1);
      if (i < N && j < M && S[i] == T[j]) chmin(newdp[j + 1], dp[j]);
    }
    if (i < N) swap(dp, newdp);
  }
  return dp[M];
}

#line 1 "string/edit_distance.hpp"
template <typename STRING>
int edit_distance(STRING& S, STRING& T) {
  int N = len(S), M = len(T);
  vc<int> dp(M + 1, 1 << 30);
  dp[0] = 0;
  FOR(i, N + 1) {
    vc<int> newdp(M + 1, 1 << 30);
    FOR(j, M + 1) {
      if (i < N) chmin(newdp[j], dp[j] + 1);
      if (j < M) chmin(dp[j + 1], dp[j] + 1);
      if (i < N && j < M) chmin(newdp[j + 1], dp[j] + 1);
      if (i < N && j < M && S[i] == T[j]) chmin(newdp[j + 1], dp[j]);
    }
    if (i < N) swap(dp, newdp);
  }
  return dp[M];
}