duval_rs/
lib.rs

1pub fn duval(s: &str) -> Vec<String> {
2    let n: usize = s.len();
3    let mut i: usize = 0;
4    let mut factorization: Vec<String> = Vec::new();
5    while i < n {
6        let mut j: usize = i + 1;
7        let mut k: usize = i;
8        while j < n && s.as_bytes()[k] <= s.as_bytes()[j] {
9            if s.as_bytes()[k] < s.as_bytes()[j] {
10                k = i;
11            } else {
12                k += 1;
13            }
14            j += 1;
15        }
16        while i <= k {
17            factorization.push(s[i..j].to_string());
18            i += j - k;
19        }
20    }
21    factorization
22}
23
24pub fn min_rotation(s: &[u8]) -> usize {
25    let mut a: usize = 0;
26    let n: usize = s.len();
27    let mut b: usize = 0;
28    while b < n {
29        let mut i: usize = 0;
30        while a + i < n {
31            let sai: u8 = s[a + i];
32            let sbi: u8 = s[if b + i < n { b + i } else { b + i - n }];
33            if a + i == b || sai < sbi {
34                if i > 1 {
35                    b += i - 1;
36                }
37                break;
38            }
39            if sai > sbi {
40                a = b;
41                break;
42            }
43            i += 1;
44        }
45        b += 1;
46    }
47    a
48}
49
50#[cfg(test)]
51mod tests {
52    use super::*;
53    use rand::Rng;
54    use rand::SeedableRng;
55
56    fn generate_random_string(length: usize, seed: u64) -> Vec<u8> {
57        const CHARACTERS: &[u8] = b"ACGT";
58        let mut rng: rand::rngs::StdRng = rand::rngs::StdRng::seed_from_u64(seed);
59
60        (0..length)
61            .map(|_| {
62                let idx: usize = rng.gen_range(0..CHARACTERS.len());
63                CHARACTERS[idx]
64            })
65            .collect()
66    }
67
68    fn min_rotation_naive(s: &[u8]) -> usize {
69        let n: usize = s.len();
70        let mut smin: Vec<u8> = s.to_vec();
71        let mut s_clone: Vec<u8> = s.to_vec();
72        let mut imin: usize = 0;
73        for i in 1..n {
74            s_clone.rotate_left(1);
75            if s_clone < smin {
76                smin = s_clone.clone();
77                imin = i;
78            }
79        }
80        imin
81    }
82
83    #[test]
84    fn test_min_rotation() {
85        const N_TESTS: u32 = 100000;
86        const N: usize = 10;
87
88        for test in 0..N_TESTS {
89            let s: Vec<u8> = generate_random_string(N, test as u64);
90            assert_eq!(min_rotation(&s), min_rotation_naive(&s));
91        }
92    }
93
94    #[test]
95    fn test_min_rotation_large() {
96        const N_TESTS: u32 = 10000;
97        const N: usize = 10000;
98
99        let mut strings: Vec<Vec<u8>> = vec![vec![b'A'; N]; N_TESTS as usize];
100        for test in 0..N_TESTS / 2 {
101            strings[test as usize] = generate_random_string(N, test as u64);
102        }
103
104        let mut sum = 0;
105        let start = std::time::Instant::now();
106        for s in strings {
107            sum += min_rotation(&s);
108        }
109        let duration = start.elapsed();
110        // assert sum != 0 to avoid compiler optimizations
111        assert_ne!(sum, 0);
112        println!("Time: {:?}", duration);
113    }
114}
duval_rs/lib.rs

duval_rs/
lib.rs
