rust_algorithm/
lib.rs

1#[cfg(test)]
2mod tests {
3    use super::Algorithm;
4    #[test]
5    fn test_gcd_of_strings() {
6        let result = Algorithm::gcd_of_strings(String::from("ABCABCABC"), String::from("ABC"));
7        assert_eq!(result.is_some(), true);
8        assert_eq!(result.unwrap(), "ABC");
9
10        let result1 = Algorithm::gcd_of_strings(String::from("HAHA"), String::from("ABC"));
11        assert_eq!(result1.is_none(), true);
12    }
13
14    #[test]
15    fn test_gcd() {
16        let result = Algorithm::gcd(8, 4);
17        assert_eq!(result, 4);
18
19        let result1 = Algorithm::gcd(8, 6);
20        assert_eq!(result1, 2);
21    }
22}
23
24pub struct Algorithm {}
25
26impl Algorithm {
27    /// 求两个字符串的最大公约字符串
28    ///
29    /// # Arguments
30    ///
31    /// * `str1` - 第一个字符串
32    /// * `str2` - 第二个字符串
33    ///
34    /// # Examples
35    ///
36    /// ```rust
37    /// use rust_algorithm::Algorithm;
38    /// let result = Algorithm::gcd_of_strings(String::from("ABCABCABC"), String::from("ABC"));
39    /// assert_eq!(result.unwrap(), "ABC");
40    /// ```
41    pub fn gcd_of_strings(str1: String, str2: String) -> Option<String> {
42        // 先算出两者长度的最大公约数
43        let str1_len = str1.len();
44        let str2_len = str2.len();
45        let gcd_result = Self::gcd(str1_len as i32, str2_len as i32);
46        // 取出公约数长度的前缀串
47        let prefix_str: String = str1.chars().take(gcd_result as usize).collect();
48        // 两个字符串必须都可以通过前缀串自我拼接多次得到
49        if Self::gcd_of_strings_check(prefix_str.clone(), str1, gcd_result)
50            && Self::gcd_of_strings_check(prefix_str.clone(), str2, gcd_result)
51        {
52            return Some(prefix_str);
53        }
54        return None;
55    }
56
57    fn gcd_of_strings_check(prefix_str: String, str1: String, gcd_result: i32) -> bool {
58        let mut temp_str: String = String::from("");
59        let mut result: bool = false;
60        for _ in 1..=str1.len() as i32 / gcd_result {
61            temp_str += &prefix_str; // &String可以自动转换为一个&str。这个功能叫做Deref转换
62            if str1 == temp_str {
63                result = true;
64                break;
65            }
66        }
67        return result;
68    }
69
70    /// 求两个数的最大公约数（greatest common divisor）
71    ///
72    /// # Arguments
73    ///
74    /// * `int1` - 第一个数
75    /// * `int2` - 第二个数
76    ///
77    /// # Examples
78    ///
79    /// ```rust
80    /// use rust_algorithm::Algorithm;
81    /// let result = Algorithm::gcd(8, 4);
82    /// assert_eq!(result, 4);
83    /// ```
84    pub fn gcd(int1: i32, int2: i32) -> i32 {
85        if int1 % int2 == 0 {
86            return int2;
87        } else {
88            return Self::gcd(int2, int1 % int2);
89        }
90    }
91}
rust_algorithm/lib.rs

rust_algorithm/
lib.rs
