rust_edit-distance.rs

use std::time::{Duration, Instant};
use std::io::{self};

fn edit_distance(a: &str, b: &str) -> u32 {
    let len_a = a.len() + 1;
    let len_b = b.len() + 1;

    let seq_a: Vec<char> = a.chars().collect();
    let seq_b: Vec<char> = b.chars().collect();

    let mut d: Vec<Vec<u32>> = vec![vec![0; len_b]; len_a];

    for i in 0..len_a { d[i][0] = i as u32; }
    for j in 0..len_b { d[0][j] = j as u32; }

    for i in 1..len_a {
        for j in 1..len_b {
            let w: u32 = if seq_a[i-1] == seq_b[j-1] { 0 } else { 1 };

            let edit_operations = [
                d[i-1][j] + 1,
                d[i][j-1] + 1,
                d[i-1][j-1] + w
            ];

            d[i][j] = *edit_operations.iter().min().unwrap();
        }
    }

    d[len_a - 1][len_b - 1]
}

fn main() {
    let instant_now = Instant::now();

    let mut a = String::new();
    let mut b = String::new();

    io::stdin().read_line(&mut a).expect("Cannot read from stdin!");
    io::stdin().read_line(&mut b).expect("Cannot read from stdin!");
    
    a = a.trim_end().to_string();
    println!("{}", edit_distance(&a, &b));

    let instant_now_now = Instant::now();
    println!("{:?}", instant_now_now.duration_since(instant_now));
}