1 //! Longest common subsequence 2 use crate::{Algorithm, Result}; 3 use alloc::vec; 4 use alloc::vec::Vec; 5 6 /// The length of the [Longest common subsequence]. 7 /// 8 /// It differs from the [`LCSStr`](crate::LCSStr). Unlike substrings, subsequences are not required 9 /// to occupy consecutive positions within the original sequences. 10 /// 11 /// [Longest common subsequence]: https://en.wikipedia.org/wiki/Longest_common_subsequence 12 #[derive(Default)] 13 pub struct LCSSeq {} 14 15 impl Algorithm<usize> for LCSSeq { for_vec<E: Eq>(&self, s1: &[E], s2: &[E]) -> Result<usize>16 fn for_vec<E: Eq>(&self, s1: &[E], s2: &[E]) -> Result<usize> { 17 let l1 = s1.len(); 18 let l2 = s2.len(); 19 let mut lengths = vec![vec![0; l2 + 1]; l1 + 1]; 20 21 for (i, char1) in s1.iter().enumerate() { 22 for (j, char2) in s2.iter().enumerate() { 23 lengths[i + 1][j + 1] = if char1 == char2 { 24 lengths[i][j] + 1 25 } else { 26 lengths[i + 1][j].max(lengths[i][j + 1]) 27 }; 28 } 29 } 30 31 let mut result = Vec::<&E>::new(); 32 let mut i = l1; 33 let mut j = l2; 34 while i != 0 && j != 0 { 35 if lengths[i][j] == lengths[i - 1][j] { 36 i -= 1; 37 } else if lengths[i][j] == lengths[i][j - 1] { 38 j -= 1; 39 } else { 40 assert!(s1[i - 1] == s2[j - 1]); 41 result.push(&s1[i - 1]); 42 i -= 1; 43 j -= 1; 44 } 45 } 46 // val: Some(result.into_iter().rev().collect::<String>()) 47 Result { 48 abs: result.len(), 49 is_distance: false, 50 max: l1.max(l2), 51 len1: l1, 52 len2: l2, 53 } 54 } 55 } 56 57 #[cfg(test)] 58 mod tests { 59 use crate::str::lcsseq; 60 use assert2::assert; 61 use proptest::prelude::*; 62 use rstest::rstest; 63 64 #[rstest] 65 #[case("", "", 0)] 66 #[case("", "abcd", 0)] 67 #[case("abcd", "", 0)] 68 #[case("ab", "cd", 0)] 69 #[case("abcd", "abcd", 4)] // "abcd" 70 #[case("test", "text", 3)] // "tet" 71 #[case("thisisatest", "testing123testing", 7)] // "tsitest" 72 #[case("abcd", "c", 1)] // "c" 73 #[case("abcd", "d", 1)] // "d" 74 #[case("abcd", "e", 0)] // "" 75 #[case("abcdefghi", "acegi", 5)] // "acegi" 76 #[case("abcdgh", "aedfhr", 3)] // "adh" 77 #[case("aggtab", "gxtxayb", 4)] // "gtab" 78 #[case("你好，世界", "再见世界", 2)] // "世界" function_str(#[case] s1: &str, #[case] s2: &str, #[case] exp: usize)79 fn function_str(#[case] s1: &str, #[case] s2: &str, #[case] exp: usize) { 80 assert!(lcsseq(s1, s2) == exp); 81 } 82 83 proptest! { 84 #[test] 85 fn prop(s1 in ".*", s2 in ".*") { 86 let res = lcsseq(&s1, &s2); 87 let res2 = lcsseq(&s2, &s1); 88 prop_assert_eq!(res, res2); 89 prop_assert!(res <= s1.len() || res <= s2.len()); 90 } 91 } 92 } 93