編集距離 O(N^2) DP

• Quiz
  • https://yukicoder.me/problems/no/225
• AC
  • https://yukicoder.me/submissions/408789
• 解説
  • 編集距離そのものの問題
  • 編集距離で可能な操作：文字の挿入・削除・置換

int dp[1050][1050];

// dp[i][j]として
i : sのi文字目
j : tのj文字目
までを一致させるための最小コスト

• としてDPで解く
• 計算量：O(NM) (N,Mは文字列の長さ)

code

// 編集距離
const int MAX_LEN = 1050;
ll edit_distance(string& s, string& t){
  ll N = s.size();
  ll M = t.size();
  VV dp(MAX_LEN, VI(MAX_LEN, inf));
  rep(i, MAX_LEN){
    dp[0][i] = i;
    dp[i][0] = i;
  }

  rep(i, N){
    rep(j, M){
      if(s[i]==t[j]){
        ll a = dp[i][j];
        ll b = dp[i][j+1] + 1;
        ll c = dp[i+1][j] + 1;
        dp[i+1][j+1] = min({a, b, c});
      }else{
        ll a = dp[i][j] + 1;
        ll b = dp[i][j+1] + 1;
        ll c = dp[i+1][j] + 1;
        dp[i+1][j+1] = min({a, b, c});
      }
    }
  }
  return dp[N][M];
}

類題

E - Sequence Matching https://atcoder.jp/contests/abc185/tasks/abc185_e