haar_lib/algo/
edit_distance.rs

1//! 編集距離
2
3#![allow(clippy::needless_range_loop)]
4
5use crate::chmin;
6use std::cmp::min;
7
8/// 編集距離
9///
10/// **Time complexity** $O(nm)$
11pub fn edit_distance<T: PartialEq>(a: &[T], b: &[T]) -> usize {
12    let n = a.len();
13    let m = b.len();
14    let mut dp = vec![vec![0; m + 1]; n + 1];
15
16    for i in 0..=n {
17        dp[i][0] = i;
18    }
19    for i in 0..=m {
20        dp[0][i] = i;
21    }
22
23    for i in 0..n {
24        for j in 0..m {
25            dp[i + 1][j + 1] = min(dp[i][j + 1] + 1, dp[i + 1][j] + 1);
26
27            if a[i] == b[j] {
28                chmin!(dp[i + 1][j + 1], dp[i][j]);
29            } else {
30                chmin!(dp[i + 1][j + 1], dp[i][j] + 1);
31            }
32        }
33    }
34
35    dp[n][m]
36}
37
38#[cfg(test)]
39mod tests {
40    use super::*;
41
42    #[test]
43    fn test() {
44        assert_eq!(edit_distance("acac".as_bytes(), "acm".as_bytes()), 2);
45        assert_eq!(edit_distance("icpc".as_bytes(), "icpc".as_bytes()), 0);
46    }
47}
haar_lib/algo/edit_distance.rs

haar_lib/algo/
edit_distance.rs
