trie/
lib.rs

1//! # Trie, Suffix Tree & Suffix Array (Rust)
2
3/// 1163h Last Substring in Lexicographical Order
4struct Sol1163 {}
5
6impl Sol1163 {
7    pub fn last_substring(s: String) -> String {
8        fn suffix_array(s: String) -> Vec<i32> {
9            let n = s.len();
10
11            let mut pfx_arr: Vec<i32> = s
12                .as_bytes()
13                .iter()
14                .map(|&chr| (chr - b'a') as i32)
15                .collect();
16
17            let mut k = 1;
18            let mut l = vec![(0, 0, 0); n];
19            while (k >> 1) < n {
20                let mut p = vec![0; n];
21
22                for (i, t) in l.iter_mut().enumerate() {
23                    t.0 = pfx_arr[i];
24                    t.1 = if i + k < n { pfx_arr[i + k] } else { -1 };
25                    t.2 = i;
26                }
27                println!("-> {k} {l:?}");
28
29                l.sort_by(|a, b| {
30                    if a.0 == b.0 {
31                        a.1.cmp(&b.1)
32                    } else {
33                        a.0.cmp(&b.0)
34                    }
35                });
36                println!("-> {k} {l:?}");
37
38                for i in 0..n {
39                    p[l[i].2] = if i > 0 && l[i].0 == l[i - 1].0 && l[i].1 == l[i - 1].1 {
40                        p[l[i - 1].2]
41                    } else {
42                        i as i32
43                    };
44                }
45
46                pfx_arr = p;
47                k <<= 1;
48            }
49
50            println!(
51                "-> {}",
52                s.chars()
53                    .skip(pfx_arr.iter().position(|&i| i as usize + 1 == n).unwrap())
54                    .collect::<String>()
55            );
56
57            pfx_arr
58        }
59        println!("-> Suffix Array: {:?}", suffix_array(s.clone()));
60
61        let (mut i, mut j, mut k) = (0, 1, 0);
62
63        let s: Vec<_> = s.chars().collect();
64        let n = s.len();
65
66        use std::cmp::Ordering::*;
67        while j + k < n {
68            match s[i + k].cmp(&s[j + k]) {
69                Equal => k += 1,
70                Greater => {
71                    j += k + 1;
72                    k = 0;
73                }
74                Less => {
75                    i = (i + k + 1).max(j);
76                    j = i + 1;
77                    k = 0;
78                }
79            }
80        }
81
82        s.iter().skip(i).collect()
83    }
84}
85
86#[cfg(test)]
87mod tests;
trie/lib.rs

trie/
lib.rs
