1 //! Longest common substring 2 use crate::{Algorithm, Result}; 3 use alloc::vec; 4 5 /// The length of the [Longest common substring]. 6 /// 7 /// A longest common substring of two or more strings is a longest string 8 /// that is a substring of all of them. 9 /// 10 /// [Longest common substring]: https://en.wikipedia.org/wiki/Longest_common_substring 11 #[derive(Default)] 12 pub struct LCSStr {} 13 14 impl Algorithm<usize> for LCSStr { for_vec<E: Eq>(&self, s1: &[E], s2: &[E]) -> Result<usize>15 fn for_vec<E: Eq>(&self, s1: &[E], s2: &[E]) -> Result<usize> { 16 let l1 = s1.len(); 17 let l2 = s2.len(); 18 let mut dp = vec![vec![0; l2 + 1]; l1 + 1]; 19 // let mut result_end = 0; 20 let mut result_len = 0; 21 for (i, c1) in s1.iter().enumerate() { 22 for (j, c2) in s2.iter().enumerate() { 23 if c1 == c2 { 24 let new_len = dp[i][j] + 1; 25 dp[i + 1][j + 1] = new_len; 26 if new_len > result_len { 27 result_len = new_len; 28 // result_end = i + 1; 29 }; 30 } 31 } 32 } 33 // s1[(result_end - result_len)..result_end].to_vec() 34 Result { 35 abs: result_len, 36 is_distance: false, 37 max: l1.max(l2), 38 len1: l1, 39 len2: l2, 40 } 41 } 42 } 43 44 #[cfg(test)] 45 mod tests { 46 use crate::str::lcsstr; 47 use assert2::assert; 48 use proptest::prelude::*; 49 use rstest::rstest; 50 51 #[rstest] 52 #[case("", "", "")] 53 #[case("a", "", "")] 54 #[case("", "a", "")] 55 #[case("a", "a", "a")] 56 #[case("ab", "b", "b")] 57 #[case("abcdef", "bcd", "bcd")] 58 #[case("bcd", "abcdef", "bcd")] 59 #[case("abcdef", "xabded", "ab")] 60 #[case("GeeksforGeeks", "GeeksQuiz", "Geeks")] 61 #[case("abcdxyz", "xyzabcd", "abcd")] 62 #[case("zxabcdezy", "yzabcdezx", "abcdez")] 63 #[case("OldSite:GeeksforGeeks.org", "NewSite:GeeksQuiz.com", "Site:Geeks")] function_str(#[case] s1: &str, #[case] s2: &str, #[case] exp: &str)64 fn function_str(#[case] s1: &str, #[case] s2: &str, #[case] exp: &str) { 65 assert!(lcsstr(s1, s2) == exp.len()); 66 } 67 68 #[test] unicode()69 fn unicode() { 70 let f = lcsstr; 71 assert!(f("п", "") == 0); 72 assert!(f("", "п") == 0); 73 assert!(f("п", "п") == 1); 74 assert!(f("привет", "пока") == 1); 75 assert!(f("корвет", "привет") == 3); 76 } 77 78 proptest! { 79 #[test] 80 fn prop(s1 in ".*", s2 in ".*") { 81 let res = lcsstr(&s1, &s2); 82 let res2 = lcsstr(&s2, &s1); 83 prop_assert_eq!(res, res2); 84 prop_assert!(res <= s1.len() || res <= s2.len()); 85 } 86 } 87 } 88