fn induced_sort(
s: &[usize],
upper: usize,
is_s: &[bool],
lms: &[usize],
) -> Vec<usize>Examples found in repository?
crates/competitive/src/string/suffix_array.rs (line 169)
140fn sa_is(s: &[usize], upper: usize) -> Vec<usize> {
141 let n = s.len();
142 match n {
143 0 => return vec![],
144 1 => return vec![0],
145 _ => {}
146 }
147
148 let mut is_s = vec![false; n];
149 is_s[n - 1] = true;
150 for i in (0..n - 1).rev() {
151 is_s[i] = if s[i] < s[i + 1] {
152 true
153 } else if s[i] > s[i + 1] {
154 false
155 } else {
156 is_s[i + 1]
157 };
158 }
159
160 let mut lms_map = vec![!0; n];
161 let mut lms = vec![];
162 for i in 1..n {
163 if is_s[i] && !is_s[i - 1] {
164 lms_map[i] = lms.len();
165 lms.push(i);
166 }
167 }
168
169 let mut sa = induced_sort(s, upper, &is_s, &lms);
170
171 if lms.len() > 1 {
172 let mut rec_s = vec![0usize; lms.len()];
173 let mut rec_upper = 0usize;
174 let mut prev = !0usize;
175 for &pos in &sa {
176 if pos != !0 && lms_map[pos] != !0 {
177 if prev != !0 {
178 let mut offset = 0usize;
179 loop {
180 if s[prev + offset] != s[pos + offset]
181 || is_s[prev + offset] != is_s[pos + offset]
182 {
183 rec_upper += 1;
184 break;
185 }
186 if offset != 0 {
187 let prev_is_lms = lms_map[prev + offset] != !0;
188 let pos_is_lms = lms_map[pos + offset] != !0;
189 if prev_is_lms || pos_is_lms {
190 rec_upper += (prev_is_lms != pos_is_lms) as usize;
191 break;
192 }
193 }
194 offset += 1;
195 }
196 }
197 rec_s[lms_map[pos]] = rec_upper;
198 prev = pos;
199 }
200 }
201
202 let rec_sa = if rec_upper + 1 == lms.len() {
203 let mut rec_sa = vec![0usize; lms.len()];
204 for i in 0..lms.len() {
205 rec_sa[rec_s[i]] = i;
206 }
207 rec_sa
208 } else {
209 sa_is(&rec_s, rec_upper)
210 };
211
212 let mut ordered_lms = Vec::with_capacity(lms.len());
213 for &i in &rec_sa {
214 ordered_lms.push(lms[i]);
215 }
216 sa = induced_sort(s, upper, &is_s, &ordered_lms);
217 }
218
219 sa
220}