Why not login to Qiita and try out its useful features?

We'll deliver articles that match you.

You can read useful information later.

0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

レーベンシュタイン距離

Posted at

問題

変更 ⇒ Sが1つ消え、Tが1つ増える(基本的に使用)

削除 ⇒ Sが1つ消える(Sの文字が多いときのみ)

挿入 ⇒ Tが1つ増える(Sの文字が少ないときのみ)

// 入力
int n, m;
string S, T;

// DP テーブル
int dp[1010][1010]; //[S : i番目][T : j番目]

int main() {
  cin >> S >> T;

  // 初期化
  for (int i = 0; i < 1010; ++i) for (int j = 0; j < 1010; ++j) dp[i][j] = INF;
  dp[0][0] = 0;

  for (int i = -1; i < (int)S.size(); ++i) {
    for (int j = -1; j < (int)T.size(); ++j) {
      if (i == -1 && j == -1) continue;   //dp[0][0] 
      if (i >= 0 && j >= 0) { //変更
        if (S[i] == T[j]) dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j]); //既に同じ
        else dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + 1); //異なる
      }
      if (i >= 0) dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j+1] + 1); //削除
      if (j >= 0) dp[i+1][j+1] = min(dp[i+1][j+1], dp[i+1][j] + 1); //挿入
    }
  }

  cout << dp[S.size()][T.size()] << endl;
}
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up

Qiita Advent Calendar is held!

Qiita Advent Calendar is an article posting event where you post articles by filling a calendar 🎅

Some calendars come with gifts and some gifts are drawn from all calendars 👀

Please tie the article to your calendar and let's enjoy Christmas together!

0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?