Skip to main content

StringSearch

competitive::string::string_search

Struct StringSearch 

Source 
pub struct StringSearch<T> {
    text: Vec<T>,
    suffix_array: SuffixArray,
    lcp_array: Vec<usize>,
    rank: Vec<usize>,
    rmq: RangeMinimumQuery<usize>,
}

Fields§

§text: Vec<T>§suffix_array: SuffixArray§lcp_array: Vec<usize>§rank: Vec<usize>§rmq: RangeMinimumQuery<usize>

Implementations§

Source§

impl<T> StringSearch<T>
where T: Ord,

Source

pub fn new(text: Vec<T>) -> Self

Examples found in repository?
crates/library_checker/src/string/number_of_substrings.rs (line 11)
6pub fn number_of_substrings(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, s: Chars);
10    let n = s.len();
11    let search = StringSearch::new(s);
12    let mut ans = n * (n + 1) / 2;
13    for &x in search.lcp_array() {
14        ans -= x;
15    }
16    writeln!(writer, "{}", ans).ok();
17}
More examples
Hide additional examples
crates/competitive/src/string/string_search.rs (line 304)
287    pub fn new(texts: Vec<Vec<T>>) -> Self {
288        assert!(!texts.is_empty());
289        let total_len: usize = texts.iter().map(|text| text.len() + 1).sum();
290        let mut concat = Vec::with_capacity(total_len - 1);
291        let mut offsets = Vec::with_capacity(texts.len());
292        let mut position_map = Vec::with_capacity(total_len);
293        for (i, text) in texts.iter().enumerate() {
294            offsets.push(concat.len());
295            for (pos, value) in text.iter().cloned().enumerate() {
296                concat.push(Delimited::Value(value));
297                position_map.push((i, pos));
298            }
299            if i + 1 < texts.len() {
300                concat.push(Delimited::Separator(!i));
301            }
302            position_map.push((i, text.len()));
303        }
304        let search = StringSearch::new(concat);
305        Self {
306            texts,
307            offsets,
308            position_map,
309            search,
310        }
311    }
Source

pub fn text(&self) -> &[T]

Source

pub fn suffix_array(&self) -> &SuffixArray

Source

pub fn lcp_array(&self) -> &[usize]

Examples found in repository?
crates/library_checker/src/string/number_of_substrings.rs (line 13)
6pub fn number_of_substrings(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, s: Chars);
10    let n = s.len();
11    let search = StringSearch::new(s);
12    let mut ans = n * (n + 1) / 2;
13    for &x in search.lcp_array() {
14        ans -= x;
15    }
16    writeln!(writer, "{}", ans).ok();
17}
Source

pub fn rank(&self) -> &[usize]

Source

pub fn longest_common_prefix(&self, a: Range<usize>, b: Range<usize>) -> usize

Examples found in repository?
crates/competitive/src/string/string_search.rs (line 324)
317    pub fn longest_common_prefix(
318        &self,
319        a: (usize, Range<usize>),
320        b: (usize, Range<usize>),
321    ) -> usize {
322        let a = self.to_global_range(a);
323        let b = self.to_global_range(b);
324        self.search.longest_common_prefix(a, b)
325    }
Source

pub fn compare(&self, a: Range<usize>, b: Range<usize>) -> Ordering

Examples found in repository?
crates/competitive/src/string/string_search.rs (line 223)
216    fn geq_suffix(&self, range: Range<usize>) -> usize {
217        let n = self.text.len();
218        debug_assert!(range.start <= range.end && range.end <= n);
219        let mut l = 0usize;
220        let mut r = n;
221        while r - l > 1 {
222            let m = (l + r) >> 1;
223            let ord = self.compare(self.suffix_array[m]..n, range.start..range.end);
224            if matches!(ord, Ordering::Less) {
225                l = m;
226            } else {
227                r = m;
228            }
229        }
230        r
231    }
232}
233
234#[derive(Debug)]
235pub struct KthSubstrings<'a, T> {
236    search: &'a StringSearch<T>,
237    prefix: Vec<u64>,
238}
239
240impl<'a, T> KthSubstrings<'a, T>
241where
242    T: Ord,
243{
244    fn new(search: &'a StringSearch<T>) -> Self {
245        let n = search.text.len();
246        let mut prefix = Vec::with_capacity(n + 1);
247        prefix.push(0);
248        let mut total = 0u64;
249        for i in 1..=n {
250            total += (n - search.suffix_array[i] - search.lcp_array[i - 1]) as u64;
251            prefix.push(total);
252        }
253        Self { search, prefix }
254    }
255
256    pub fn kth_distinct_substring(&self, k: u64) -> Option<Range<usize>> {
257        let idx = self.prefix.partition_point(|&x| x <= k);
258        if idx == self.prefix.len() {
259            return None;
260        }
261        debug_assert!(idx > 0);
262        let start = self.search.suffix_array[idx];
263        let len = self.search.lcp_array[idx - 1] + (k - self.prefix[idx - 1]) as usize + 1;
264        Some(start..start + len)
265    }
266
267    pub fn index_of_distinct_substring(&self, range: Range<usize>) -> u64 {
268        debug_assert!(range.start < range.end && range.end <= self.search.text.len());
269        let m = range.len();
270        let idx = self.search.geq_suffix(range);
271        self.prefix[idx - 1] + (m - self.search.lcp_array[idx - 1] - 1) as u64
272    }
273}
274
275#[derive(Debug)]
276pub struct MultipleStringSearch<T> {
277    texts: Vec<Vec<T>>,
278    offsets: Vec<usize>,
279    position_map: Vec<(usize, usize)>,
280    search: StringSearch<Delimited<T>>,
281}
282
283impl<T> MultipleStringSearch<T>
284where
285    T: Ord + Clone,
286{
287    pub fn new(texts: Vec<Vec<T>>) -> Self {
288        assert!(!texts.is_empty());
289        let total_len: usize = texts.iter().map(|text| text.len() + 1).sum();
290        let mut concat = Vec::with_capacity(total_len - 1);
291        let mut offsets = Vec::with_capacity(texts.len());
292        let mut position_map = Vec::with_capacity(total_len);
293        for (i, text) in texts.iter().enumerate() {
294            offsets.push(concat.len());
295            for (pos, value) in text.iter().cloned().enumerate() {
296                concat.push(Delimited::Value(value));
297                position_map.push((i, pos));
298            }
299            if i + 1 < texts.len() {
300                concat.push(Delimited::Separator(!i));
301            }
302            position_map.push((i, text.len()));
303        }
304        let search = StringSearch::new(concat);
305        Self {
306            texts,
307            offsets,
308            position_map,
309            search,
310        }
311    }
312
313    pub fn texts(&self) -> &[Vec<T>] {
314        &self.texts
315    }
316
317    pub fn longest_common_prefix(
318        &self,
319        a: (usize, Range<usize>),
320        b: (usize, Range<usize>),
321    ) -> usize {
322        let a = self.to_global_range(a);
323        let b = self.to_global_range(b);
324        self.search.longest_common_prefix(a, b)
325    }
326
327    pub fn compare(&self, a: (usize, Range<usize>), b: (usize, Range<usize>)) -> Ordering {
328        let a = self.to_global_range(a);
329        let b = self.to_global_range(b);
330        self.search.compare(a, b)
331    }
Source

pub fn range(&self, pattern: &[T]) -> Range<usize>

Source

pub fn positions( &self, range: Range<usize>, ) -> impl DoubleEndedIterator<Item = usize> + '_

Source

pub fn kth_substrings(&self) -> KthSubstrings<'_, T>

Source

fn lcp_suffix(&self, a: usize, b: usize) -> usize

Examples found in repository?
crates/competitive/src/string/string_search.rs (line 105)
101    pub fn longest_common_prefix(&self, a: Range<usize>, b: Range<usize>) -> usize {
102        debug_assert!(a.start <= a.end && a.end <= self.text.len());
103        debug_assert!(b.start <= b.end && b.end <= self.text.len());
104        let len = (a.end - a.start).min(b.end - b.start);
105        self.lcp_suffix(a.start, b.start).min(len)
106    }
107
108    pub fn compare(&self, a: Range<usize>, b: Range<usize>) -> Ordering {
109        debug_assert!(a.start <= a.end && a.end <= self.text.len());
110        debug_assert!(b.start <= b.end && b.end <= self.text.len());
111        let len_a = a.end - a.start;
112        let len_b = b.end - b.start;
113        let len = len_a.min(len_b);
114        let lcp = self.lcp_suffix(a.start, b.start).min(len);
115        if lcp == len {
116            return len_a.cmp(&len_b);
117        }
118        self.text[a.start + lcp].cmp(&self.text[b.start + lcp])
119    }
Source

fn lcp_sa(&self, a: usize, b: usize) -> usize

Examples found in repository?
crates/competitive/src/string/string_search.rs (line 138)
137    fn lcp_suffix(&self, a: usize, b: usize) -> usize {
138        self.lcp_sa(self.rank[a], self.rank[b])
139    }
140
141    fn lcp_sa(&self, a: usize, b: usize) -> usize {
142        if a == b {
143            return self.text.len() - self.suffix_array[a];
144        }
145        let (l, r) = if a < b { (a, b) } else { (b, a) };
146        self.rmq.fold(l, r)
147    }
148
149    fn compare_suffix_pattern<P>(
150        &self,
151        suffix_start: usize,
152        pattern: &P,
153        start: usize,
154    ) -> (Ordering, usize)
155    where
156        P: Pattern<T> + ?Sized,
157    {
158        let n = self.text.len();
159        let m = pattern.len();
160        let mut i = start;
161        while i < m && suffix_start + i < n && pattern.eq_text(i, &self.text[suffix_start + i]) {
162            i += 1;
163        }
164        let ord = if i == m {
165            Ordering::Equal
166        } else if suffix_start + i == n {
167            Ordering::Less
168        } else {
169            pattern.cmp_text(i, &self.text[suffix_start + i])
170        };
171        (ord, i)
172    }
173
174    fn bound_prefix<P>(&self, pattern: &P, upper: bool) -> usize
175    where
176        P: Pattern<T> + ?Sized,
177    {
178        if pattern.len() == 0 {
179            return if upper { self.text.len() + 1 } else { 0 };
180        }
181        let pred = |ord: Ordering| {
182            if upper {
183                ord == Ordering::Greater
184            } else {
185                ord != Ordering::Less
186            }
187        };
188        let (cmp_last, lcp_last) =
189            self.compare_suffix_pattern(self.suffix_array[self.text.len()], pattern, 0);
190        if !pred(cmp_last) {
191            return self.text.len() + 1;
192        }
193        let mut l = 0usize;
194        let mut r = self.text.len();
195        let mut lcp_l = 0usize;
196        let mut lcp_r = lcp_last;
197        while r - l > 1 {
198            let m = (l + r) >> 1;
199            let start = match lcp_l.cmp(&lcp_r) {
200                Ordering::Less => lcp_l.min(self.lcp_sa(l, m)),
201                Ordering::Greater => lcp_r.min(self.lcp_sa(m, r)),
202                Ordering::Equal => lcp_l,
203            };
204            let (cmp_m, lcp_m) = self.compare_suffix_pattern(self.suffix_array[m], pattern, start);
205            if pred(cmp_m) {
206                r = m;
207                lcp_r = lcp_m;
208            } else {
209                l = m;
210                lcp_l = lcp_m;
211            }
212        }
213        r
214    }
Source

fn compare_suffix_pattern<P>( &self, suffix_start: usize, pattern: &P, start: usize, ) -> (Ordering, usize)
where P: Pattern<T> + ?Sized,

Examples found in repository?
crates/competitive/src/string/string_search.rs (line 189)
174    fn bound_prefix<P>(&self, pattern: &P, upper: bool) -> usize
175    where
176        P: Pattern<T> + ?Sized,
177    {
178        if pattern.len() == 0 {
179            return if upper { self.text.len() + 1 } else { 0 };
180        }
181        let pred = |ord: Ordering| {
182            if upper {
183                ord == Ordering::Greater
184            } else {
185                ord != Ordering::Less
186            }
187        };
188        let (cmp_last, lcp_last) =
189            self.compare_suffix_pattern(self.suffix_array[self.text.len()], pattern, 0);
190        if !pred(cmp_last) {
191            return self.text.len() + 1;
192        }
193        let mut l = 0usize;
194        let mut r = self.text.len();
195        let mut lcp_l = 0usize;
196        let mut lcp_r = lcp_last;
197        while r - l > 1 {
198            let m = (l + r) >> 1;
199            let start = match lcp_l.cmp(&lcp_r) {
200                Ordering::Less => lcp_l.min(self.lcp_sa(l, m)),
201                Ordering::Greater => lcp_r.min(self.lcp_sa(m, r)),
202                Ordering::Equal => lcp_l,
203            };
204            let (cmp_m, lcp_m) = self.compare_suffix_pattern(self.suffix_array[m], pattern, start);
205            if pred(cmp_m) {
206                r = m;
207                lcp_r = lcp_m;
208            } else {
209                l = m;
210                lcp_l = lcp_m;
211            }
212        }
213        r
214    }
Source

fn bound_prefix<P>(&self, pattern: &P, upper: bool) -> usize
where P: Pattern<T> + ?Sized,

Examples found in repository?
crates/competitive/src/string/string_search.rs (line 122)
121    pub fn range(&self, pattern: &[T]) -> Range<usize> {
122        let left = self.bound_prefix(pattern, false);
123        let right = self.bound_prefix(pattern, true);
124        left..right
125    }
126
127    pub fn positions(&self, range: Range<usize>) -> impl DoubleEndedIterator<Item = usize> + '_ {
128        debug_assert!(range.start <= range.end);
129        debug_assert!(range.end <= self.text.len() + 1);
130        range.map(move |i| self.suffix_array[i])
131    }
132
133    pub fn kth_substrings(&self) -> KthSubstrings<'_, T> {
134        KthSubstrings::new(self)
135    }
136
137    fn lcp_suffix(&self, a: usize, b: usize) -> usize {
138        self.lcp_sa(self.rank[a], self.rank[b])
139    }
140
141    fn lcp_sa(&self, a: usize, b: usize) -> usize {
142        if a == b {
143            return self.text.len() - self.suffix_array[a];
144        }
145        let (l, r) = if a < b { (a, b) } else { (b, a) };
146        self.rmq.fold(l, r)
147    }
148
149    fn compare_suffix_pattern<P>(
150        &self,
151        suffix_start: usize,
152        pattern: &P,
153        start: usize,
154    ) -> (Ordering, usize)
155    where
156        P: Pattern<T> + ?Sized,
157    {
158        let n = self.text.len();
159        let m = pattern.len();
160        let mut i = start;
161        while i < m && suffix_start + i < n && pattern.eq_text(i, &self.text[suffix_start + i]) {
162            i += 1;
163        }
164        let ord = if i == m {
165            Ordering::Equal
166        } else if suffix_start + i == n {
167            Ordering::Less
168        } else {
169            pattern.cmp_text(i, &self.text[suffix_start + i])
170        };
171        (ord, i)
172    }
173
174    fn bound_prefix<P>(&self, pattern: &P, upper: bool) -> usize
175    where
176        P: Pattern<T> + ?Sized,
177    {
178        if pattern.len() == 0 {
179            return if upper { self.text.len() + 1 } else { 0 };
180        }
181        let pred = |ord: Ordering| {
182            if upper {
183                ord == Ordering::Greater
184            } else {
185                ord != Ordering::Less
186            }
187        };
188        let (cmp_last, lcp_last) =
189            self.compare_suffix_pattern(self.suffix_array[self.text.len()], pattern, 0);
190        if !pred(cmp_last) {
191            return self.text.len() + 1;
192        }
193        let mut l = 0usize;
194        let mut r = self.text.len();
195        let mut lcp_l = 0usize;
196        let mut lcp_r = lcp_last;
197        while r - l > 1 {
198            let m = (l + r) >> 1;
199            let start = match lcp_l.cmp(&lcp_r) {
200                Ordering::Less => lcp_l.min(self.lcp_sa(l, m)),
201                Ordering::Greater => lcp_r.min(self.lcp_sa(m, r)),
202                Ordering::Equal => lcp_l,
203            };
204            let (cmp_m, lcp_m) = self.compare_suffix_pattern(self.suffix_array[m], pattern, start);
205            if pred(cmp_m) {
206                r = m;
207                lcp_r = lcp_m;
208            } else {
209                l = m;
210                lcp_l = lcp_m;
211            }
212        }
213        r
214    }
215
216    fn geq_suffix(&self, range: Range<usize>) -> usize {
217        let n = self.text.len();
218        debug_assert!(range.start <= range.end && range.end <= n);
219        let mut l = 0usize;
220        let mut r = n;
221        while r - l > 1 {
222            let m = (l + r) >> 1;
223            let ord = self.compare(self.suffix_array[m]..n, range.start..range.end);
224            if matches!(ord, Ordering::Less) {
225                l = m;
226            } else {
227                r = m;
228            }
229        }
230        r
231    }
232}
233
234#[derive(Debug)]
235pub struct KthSubstrings<'a, T> {
236    search: &'a StringSearch<T>,
237    prefix: Vec<u64>,
238}
239
240impl<'a, T> KthSubstrings<'a, T>
241where
242    T: Ord,
243{
244    fn new(search: &'a StringSearch<T>) -> Self {
245        let n = search.text.len();
246        let mut prefix = Vec::with_capacity(n + 1);
247        prefix.push(0);
248        let mut total = 0u64;
249        for i in 1..=n {
250            total += (n - search.suffix_array[i] - search.lcp_array[i - 1]) as u64;
251            prefix.push(total);
252        }
253        Self { search, prefix }
254    }
255
256    pub fn kth_distinct_substring(&self, k: u64) -> Option<Range<usize>> {
257        let idx = self.prefix.partition_point(|&x| x <= k);
258        if idx == self.prefix.len() {
259            return None;
260        }
261        debug_assert!(idx > 0);
262        let start = self.search.suffix_array[idx];
263        let len = self.search.lcp_array[idx - 1] + (k - self.prefix[idx - 1]) as usize + 1;
264        Some(start..start + len)
265    }
266
267    pub fn index_of_distinct_substring(&self, range: Range<usize>) -> u64 {
268        debug_assert!(range.start < range.end && range.end <= self.search.text.len());
269        let m = range.len();
270        let idx = self.search.geq_suffix(range);
271        self.prefix[idx - 1] + (m - self.search.lcp_array[idx - 1] - 1) as u64
272    }
273}
274
275#[derive(Debug)]
276pub struct MultipleStringSearch<T> {
277    texts: Vec<Vec<T>>,
278    offsets: Vec<usize>,
279    position_map: Vec<(usize, usize)>,
280    search: StringSearch<Delimited<T>>,
281}
282
283impl<T> MultipleStringSearch<T>
284where
285    T: Ord + Clone,
286{
287    pub fn new(texts: Vec<Vec<T>>) -> Self {
288        assert!(!texts.is_empty());
289        let total_len: usize = texts.iter().map(|text| text.len() + 1).sum();
290        let mut concat = Vec::with_capacity(total_len - 1);
291        let mut offsets = Vec::with_capacity(texts.len());
292        let mut position_map = Vec::with_capacity(total_len);
293        for (i, text) in texts.iter().enumerate() {
294            offsets.push(concat.len());
295            for (pos, value) in text.iter().cloned().enumerate() {
296                concat.push(Delimited::Value(value));
297                position_map.push((i, pos));
298            }
299            if i + 1 < texts.len() {
300                concat.push(Delimited::Separator(!i));
301            }
302            position_map.push((i, text.len()));
303        }
304        let search = StringSearch::new(concat);
305        Self {
306            texts,
307            offsets,
308            position_map,
309            search,
310        }
311    }
312
313    pub fn texts(&self) -> &[Vec<T>] {
314        &self.texts
315    }
316
317    pub fn longest_common_prefix(
318        &self,
319        a: (usize, Range<usize>),
320        b: (usize, Range<usize>),
321    ) -> usize {
322        let a = self.to_global_range(a);
323        let b = self.to_global_range(b);
324        self.search.longest_common_prefix(a, b)
325    }
326
327    pub fn compare(&self, a: (usize, Range<usize>), b: (usize, Range<usize>)) -> Ordering {
328        let a = self.to_global_range(a);
329        let b = self.to_global_range(b);
330        self.search.compare(a, b)
331    }
332
333    pub fn range(&self, pattern: &[T]) -> Range<usize> {
334        let pattern = DelimitedPattern { pattern };
335        let left = self.search.bound_prefix(&pattern, false);
336        let right = self.search.bound_prefix(&pattern, true);
337        left..right
338    }
Source

fn geq_suffix(&self, range: Range<usize>) -> usize

Examples found in repository?
crates/competitive/src/string/string_search.rs (line 270)
267    pub fn index_of_distinct_substring(&self, range: Range<usize>) -> u64 {
268        debug_assert!(range.start < range.end && range.end <= self.search.text.len());
269        let m = range.len();
270        let idx = self.search.geq_suffix(range);
271        self.prefix[idx - 1] + (m - self.search.lcp_array[idx - 1] - 1) as u64
272    }
273}
274
275#[derive(Debug)]
276pub struct MultipleStringSearch<T> {
277    texts: Vec<Vec<T>>,
278    offsets: Vec<usize>,
279    position_map: Vec<(usize, usize)>,
280    search: StringSearch<Delimited<T>>,
281}
282
283impl<T> MultipleStringSearch<T>
284where
285    T: Ord + Clone,
286{
287    pub fn new(texts: Vec<Vec<T>>) -> Self {
288        assert!(!texts.is_empty());
289        let total_len: usize = texts.iter().map(|text| text.len() + 1).sum();
290        let mut concat = Vec::with_capacity(total_len - 1);
291        let mut offsets = Vec::with_capacity(texts.len());
292        let mut position_map = Vec::with_capacity(total_len);
293        for (i, text) in texts.iter().enumerate() {
294            offsets.push(concat.len());
295            for (pos, value) in text.iter().cloned().enumerate() {
296                concat.push(Delimited::Value(value));
297                position_map.push((i, pos));
298            }
299            if i + 1 < texts.len() {
300                concat.push(Delimited::Separator(!i));
301            }
302            position_map.push((i, text.len()));
303        }
304        let search = StringSearch::new(concat);
305        Self {
306            texts,
307            offsets,
308            position_map,
309            search,
310        }
311    }
312
313    pub fn texts(&self) -> &[Vec<T>] {
314        &self.texts
315    }
316
317    pub fn longest_common_prefix(
318        &self,
319        a: (usize, Range<usize>),
320        b: (usize, Range<usize>),
321    ) -> usize {
322        let a = self.to_global_range(a);
323        let b = self.to_global_range(b);
324        self.search.longest_common_prefix(a, b)
325    }
326
327    pub fn compare(&self, a: (usize, Range<usize>), b: (usize, Range<usize>)) -> Ordering {
328        let a = self.to_global_range(a);
329        let b = self.to_global_range(b);
330        self.search.compare(a, b)
331    }
332
333    pub fn range(&self, pattern: &[T]) -> Range<usize> {
334        let pattern = DelimitedPattern { pattern };
335        let left = self.search.bound_prefix(&pattern, false);
336        let right = self.search.bound_prefix(&pattern, true);
337        left..right
338    }
339
340    pub fn positions(
341        &self,
342        range: Range<usize>,
343    ) -> impl DoubleEndedIterator<Item = (usize, usize)> + '_ {
344        debug_assert!(range.start <= range.end);
345        debug_assert!(range.end <= self.position_map.len());
346        range.map(move |i| self.position_map[self.search.suffix_array[i]])
347    }
348
349    pub fn kth_substrings(&self) -> MultipleKthSubstrings<'_, T> {
350        MultipleKthSubstrings::new(self)
351    }
352
353    fn to_global_range(&self, (index, range): (usize, Range<usize>)) -> Range<usize> {
354        debug_assert!(index < self.texts.len());
355        let len = self.texts[index].len();
356        debug_assert!(range.start <= range.end && range.end <= len);
357        let base = self.offsets[index];
358        base + range.start..base + range.end
359    }
360
361    fn suffix_len(&self, a: usize) -> usize {
362        let (text_idx, pos) = self.position_map[self.search.suffix_array[a]];
363        self.texts[text_idx].len() - pos
364    }
365}
366
367#[derive(Debug)]
368pub struct MultipleKthSubstrings<'a, T> {
369    search: &'a MultipleStringSearch<T>,
370    prefix: Vec<u64>,
371}
372
373impl<'a, T> MultipleKthSubstrings<'a, T>
374where
375    T: Ord + Clone,
376{
377    fn new(search: &'a MultipleStringSearch<T>) -> Self {
378        let n = search.search.text.len();
379        let mut prefix = Vec::with_capacity(n);
380        prefix.push(0);
381        let mut total = 0u64;
382        for i in 1..=n {
383            let len = search.suffix_len(i);
384            let prev_len = search.suffix_len(i - 1);
385            let lcp_prev = search.search.lcp_array[i - 1].min(len).min(prev_len);
386            total += (len - lcp_prev) as u64;
387            prefix.push(total);
388        }
389        Self { search, prefix }
390    }
391
392    pub fn kth_distinct_substring(&self, k: u64) -> Option<(usize, Range<usize>)> {
393        let idx = self.prefix.partition_point(|&x| x <= k);
394        if idx == self.prefix.len() {
395            return None;
396        }
397        let (text_idx, pos) = self.search.position_map[self.search.search.suffix_array[idx]];
398        let len = self.search.suffix_len(idx) - (self.prefix[idx] - k) as usize + 1;
399        Some((text_idx, pos..pos + len))
400    }
401
402    pub fn index_of_distinct_substring(&self, (text_idx, range): (usize, Range<usize>)) -> u64 {
403        debug_assert!(text_idx < self.search.texts.len());
404        debug_assert!(range.start < range.end && range.end <= self.search.texts[text_idx].len());
405        let m = range.len();
406        let range = self.search.to_global_range((text_idx, range));
407        let idx = self.search.search.geq_suffix(range);
408        let len = self.search.suffix_len(idx);
409        let prev_len = self.search.suffix_len(idx - 1);
410        let lcp_prev = self.search.search.lcp_array[idx - 1].min(len).min(prev_len);
411        self.prefix[idx - 1] + (m - lcp_prev - 1) as u64
412    }

Trait Implementations§

Source§

impl<T: Debug> Debug for StringSearch<T>

Source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more

Auto Trait Implementations§

§

impl<T> Freeze for StringSearch<T>

§

impl<T> RefUnwindSafe for StringSearch<T>
where T: RefUnwindSafe,

§

impl<T> Send for StringSearch<T>
where T: Send,

§

impl<T> Sync for StringSearch<T>
where T: Sync,

§

impl<T> Unpin for StringSearch<T>
where T: Unpin,

§

impl<T> UnsafeUnpin for StringSearch<T>

§

impl<T> UnwindSafe for StringSearch<T>
where T: UnwindSafe,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToArrayVecScalar for T

Source§

fn to_array_vec_scalar(self) -> ArrayVecScalar<T>

Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.