Struct MultipleStringSearch 

pub struct MultipleStringSearch<T> {
    texts: Vec<Vec<T>>,
    offsets: Vec<usize>,
    position_map: Vec<(usize, usize)>,
    search: StringSearch<Delimited<T>>,
}

Fields

texts: Vec<Vec<T>>

offsets: Vec<usize>

position_map: Vec<(usize, usize)>

search: StringSearch<Delimited<T>>

Implementations

impl<T> MultipleStringSearch<T>

where T: Ord + Clone,

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

pub fn texts(&self) -> &[Vec<T>]

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

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

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

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

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

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

Examples found in repository

crates/competitive/src/string/string_search.rs (line 322)

    pub fn longest_common_prefix(
        &self,
        a: (usize, Range<usize>),
        b: (usize, Range<usize>),
    ) -> usize {
        let a = self.to_global_range(a);
        let b = self.to_global_range(b);
        self.search.longest_common_prefix(a, b)
    }

    pub fn compare(&self, a: (usize, Range<usize>), b: (usize, Range<usize>)) -> Ordering {
        let a = self.to_global_range(a);
        let b = self.to_global_range(b);
        self.search.compare(a, b)
    }

    pub fn range(&self, pattern: &[T]) -> Range<usize> {
        let pattern = DelimitedPattern { pattern };
        let left = self.search.bound_prefix(&pattern, false);
        let right = self.search.bound_prefix(&pattern, true);
        left..right
    }

    pub fn positions(
        &self,
        range: Range<usize>,
    ) -> impl DoubleEndedIterator<Item = (usize, usize)> + '_ {
        debug_assert!(range.start <= range.end);
        debug_assert!(range.end <= self.position_map.len());
        range.map(move |i| self.position_map[self.search.suffix_array[i]])
    }

    pub fn kth_substrings(&self) -> MultipleKthSubstrings<'_, T> {
        MultipleKthSubstrings::new(self)
    }

    fn to_global_range(&self, (index, range): (usize, Range<usize>)) -> Range<usize> {
        debug_assert!(index < self.texts.len());
        let len = self.texts[index].len();
        debug_assert!(range.start <= range.end && range.end <= len);
        let base = self.offsets[index];
        base + range.start..base + range.end
    }

    fn suffix_len(&self, a: usize) -> usize {
        let (text_idx, pos) = self.position_map[self.search.suffix_array[a]];
        self.texts[text_idx].len() - pos
    }
}

#[derive(Debug)]
pub struct MultipleKthSubstrings<'a, T> {
    search: &'a MultipleStringSearch<T>,
    prefix: Vec<u64>,
}

impl<'a, T> MultipleKthSubstrings<'a, T>
where
    T: Ord + Clone,
{
    fn new(search: &'a MultipleStringSearch<T>) -> Self {
        let n = search.search.text.len();
        let mut prefix = Vec::with_capacity(n);
        prefix.push(0);
        let mut total = 0u64;
        for i in 1..=n {
            let len = search.suffix_len(i);
            let prev_len = search.suffix_len(i - 1);
            let lcp_prev = search.search.lcp_array[i - 1].min(len).min(prev_len);
            total += (len - lcp_prev) as u64;
            prefix.push(total);
        }
        Self { search, prefix }
    }

    pub fn kth_distinct_substring(&self, k: u64) -> Option<(usize, Range<usize>)> {
        let idx = self.prefix.partition_point(|&x| x <= k);
        if idx == self.prefix.len() {
            return None;
        }
        let (text_idx, pos) = self.search.position_map[self.search.search.suffix_array[idx]];
        let len = self.search.suffix_len(idx) - (self.prefix[idx] - k) as usize + 1;
        Some((text_idx, pos..pos + len))
    }

    pub fn index_of_distinct_substring(&self, (text_idx, range): (usize, Range<usize>)) -> u64 {
        debug_assert!(text_idx < self.search.texts.len());
        debug_assert!(range.start < range.end && range.end <= self.search.texts[text_idx].len());
        let m = range.len();
        let range = self.search.to_global_range((text_idx, range));
        let idx = self.search.search.geq_suffix(range);
        let len = self.search.suffix_len(idx);
        let prev_len = self.search.suffix_len(idx - 1);
        let lcp_prev = self.search.search.lcp_array[idx - 1].min(len).min(prev_len);
        self.prefix[idx - 1] + (m - lcp_prev - 1) as u64
    }

fn suffix_len(&self, a: usize) -> usize

Examples found in repository

crates/competitive/src/string/string_search.rs (line 383)

    fn new(search: &'a MultipleStringSearch<T>) -> Self {
        let n = search.search.text.len();
        let mut prefix = Vec::with_capacity(n);
        prefix.push(0);
        let mut total = 0u64;
        for i in 1..=n {
            let len = search.suffix_len(i);
            let prev_len = search.suffix_len(i - 1);
            let lcp_prev = search.search.lcp_array[i - 1].min(len).min(prev_len);
            total += (len - lcp_prev) as u64;
            prefix.push(total);
        }
        Self { search, prefix }
    }

    pub fn kth_distinct_substring(&self, k: u64) -> Option<(usize, Range<usize>)> {
        let idx = self.prefix.partition_point(|&x| x <= k);
        if idx == self.prefix.len() {
            return None;
        }
        let (text_idx, pos) = self.search.position_map[self.search.search.suffix_array[idx]];
        let len = self.search.suffix_len(idx) - (self.prefix[idx] - k) as usize + 1;
        Some((text_idx, pos..pos + len))
    }

    pub fn index_of_distinct_substring(&self, (text_idx, range): (usize, Range<usize>)) -> u64 {
        debug_assert!(text_idx < self.search.texts.len());
        debug_assert!(range.start < range.end && range.end <= self.search.texts[text_idx].len());
        let m = range.len();
        let range = self.search.to_global_range((text_idx, range));
        let idx = self.search.search.geq_suffix(range);
        let len = self.search.suffix_len(idx);
        let prev_len = self.search.suffix_len(idx - 1);
        let lcp_prev = self.search.search.lcp_array[idx - 1].min(len).min(prev_len);
        self.prefix[idx - 1] + (m - lcp_prev - 1) as u64
    }

Trait Implementations

impl<T: Debug> Debug for MultipleStringSearch<T>

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

Formats the value using the given formatter.