Rustで動的計画法 (4)

『アルゴリズムとデータ構造』を Rust で実装してみるシリーズ。5章の動的計画法。

前回 → https://quantized-cube.com/rust-dp-03

今回は編集距離。

use proconio::input;

fn input(use_default_values: bool) -> (String, String) {
    if use_default_values {
        let s = String::from("logistic");
        let t = String::from("algorithm");
        return (s, t);
    } else {
        println!("Input s and t:");
        input! {
            s: String,
            t: String,
        }
        return (s, t);
    }
}

const INF: i64 = 1 << 29; // 十分大きな値 (ここでは 2^29 とする)

fn chmin<T: PartialOrd>(a: &mut T, b: T) {
    if *a > b {
        *a = b;
    }
}

/// 編集距離を動的計画法を用いて求める
pub fn code_5_8(use_default_values: bool) -> i64 {
    // 入力
    let (s, t) = input(use_default_values);

    // DP テーブル定義
    let mut dp = vec![vec![INF; t.len() + 1]; s.len() + 1];

    // DP 初期条件
    dp[0][0] = 0;

    // DPループ
    for i in 0..s.len() + 1 {
        for j in 0..t.len() + 1 {
            // 変更操作
            if i > 0 && j > 0 {
                let b = dp[i - 1][j - 1];
                if s.as_bytes()[i - 1] == t.as_bytes()[j - 1] {
                    chmin(&mut dp[i][j], b);
                } else {
                    chmin(&mut dp[i][j], b + 1);
                }
            }

            // 削除操作
            if i > 0 {
                let b = dp[i - 1][j] + 1;
                chmin(&mut dp[i][j], b);
            };

            // 挿入操作
            if j > 0 {
                let b = dp[i][j - 1] + 1;
                chmin(&mut dp[i][j], b);
            };
        }
    }

    // 答えの出力
    dp[s.len()][t.len()]
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn code_5_8_works() {
        let result = code_5_8(true);
        assert_eq!(result, 6);
    }
}

GitHub のリポジトリはこちら https://github.com/quantized-cube/book_algorithm_solution_rust