Struct SuffixTree

Source

pub struct SuffixTree<T>where
    T: Ord,{
    text: Vec<T>,
    suffix_array: Vec<usize>,
    lcp_array: Vec<usize>,
    rank: Vec<usize>,
    nodes: Vec<STNode>,
    children: Vec<usize>,
    leafs: Vec<usize>,
    inv: Vec<usize>,
}

Fields§

§text: Vec<T>§suffix_array: Vec<usize>§lcp_array: Vec<usize>§rank: Vec<usize>§nodes: Vec<STNode>§children: Vec<usize>§leafs: Vec<usize>§inv: Vec<usize>

Implementations§

Source §

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

Source

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

Examples found in repository ?

crates/competitive/src/string/suffix_tree.rs (line 443)

425    pub fn new(texts: Vec<Vec<T>>) -> Self {
426        assert!(!texts.is_empty());
427        let total_len: usize = texts.iter().map(|text| text.len() + 1).sum();
428        let mut concat = Vec::with_capacity(total_len - 1);
429        let mut offsets = Vec::with_capacity(texts.len());
430        let mut position_map = Vec::with_capacity(total_len);
431        for (i, text) in texts.iter().enumerate() {
432            offsets.push(concat.len());
433            for (pos, value) in text.iter().cloned().enumerate() {
434                concat.push(Delimited::Value(value));
435                position_map.push((i, pos));
436            }
437            if i + 1 < texts.len() {
438                concat.push(Delimited::Separator(!i));
439            }
440            position_map.push((i, text.len()));
441        }
442
443        let mut tree = SuffixTree::new(concat);
444        for node_id in 0..tree.node_size() {
445            if tree.children(node_id).is_empty() {
446                let node = tree.node(node_id);
447                let (text_idx, pos) = position_map[tree.suffix_array()[node.sa_range.start]];
448                tree.nodes[node_id].depth = texts[text_idx].len() - pos;
449            }
450        }
451
452        Self {
453            texts,
454            offsets,
455            tree,
456            position_map,
457        }
458    }

Source

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

Source

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

Examples found in repository ?

crates/competitive/src/string/suffix_tree.rs (line 447)

425    pub fn new(texts: Vec<Vec<T>>) -> Self {
426        assert!(!texts.is_empty());
427        let total_len: usize = texts.iter().map(|text| text.len() + 1).sum();
428        let mut concat = Vec::with_capacity(total_len - 1);
429        let mut offsets = Vec::with_capacity(texts.len());
430        let mut position_map = Vec::with_capacity(total_len);
431        for (i, text) in texts.iter().enumerate() {
432            offsets.push(concat.len());
433            for (pos, value) in text.iter().cloned().enumerate() {
434                concat.push(Delimited::Value(value));
435                position_map.push((i, pos));
436            }
437            if i + 1 < texts.len() {
438                concat.push(Delimited::Separator(!i));
439            }
440            position_map.push((i, text.len()));
441        }
442
443        let mut tree = SuffixTree::new(concat);
444        for node_id in 0..tree.node_size() {
445            if tree.children(node_id).is_empty() {
446                let node = tree.node(node_id);
447                let (text_idx, pos) = position_map[tree.suffix_array()[node.sa_range.start]];
448                tree.nodes[node_id].depth = texts[text_idx].len() - pos;
449            }
450        }
451
452        Self {
453            texts,
454            offsets,
455            tree,
456            position_map,
457        }
458    }
459
460    pub fn texts(&self) -> &[Vec<T>] {
461        &self.texts
462    }
463
464    pub fn suffix_array(&self) -> &[usize] {
465        self.tree.suffix_array()
466    }

Source

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

Examples found in repository ?

crates/competitive/src/string/suffix_tree.rs (line 469)

468    pub fn lcp_array(&self) -> &[usize] {
469        self.tree.lcp_array()
470    }

Source

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

Examples found in repository ?

crates/competitive/src/string/suffix_tree.rs (line 473)

472    pub fn rank(&self) -> &[usize] {
473        self.tree.rank()
474    }

Source

pub fn node_size(&self) -> usize

Examples found in repository ?

crates/competitive/src/string/suffix_tree.rs (line 444)

425    pub fn new(texts: Vec<Vec<T>>) -> Self {
426        assert!(!texts.is_empty());
427        let total_len: usize = texts.iter().map(|text| text.len() + 1).sum();
428        let mut concat = Vec::with_capacity(total_len - 1);
429        let mut offsets = Vec::with_capacity(texts.len());
430        let mut position_map = Vec::with_capacity(total_len);
431        for (i, text) in texts.iter().enumerate() {
432            offsets.push(concat.len());
433            for (pos, value) in text.iter().cloned().enumerate() {
434                concat.push(Delimited::Value(value));
435                position_map.push((i, pos));
436            }
437            if i + 1 < texts.len() {
438                concat.push(Delimited::Separator(!i));
439            }
440            position_map.push((i, text.len()));
441        }
442
443        let mut tree = SuffixTree::new(concat);
444        for node_id in 0..tree.node_size() {
445            if tree.children(node_id).is_empty() {
446                let node = tree.node(node_id);
447                let (text_idx, pos) = position_map[tree.suffix_array()[node.sa_range.start]];
448                tree.nodes[node_id].depth = texts[text_idx].len() - pos;
449            }
450        }
451
452        Self {
453            texts,
454            offsets,
455            tree,
456            position_map,
457        }
458    }
459
460    pub fn texts(&self) -> &[Vec<T>] {
461        &self.texts
462    }
463
464    pub fn suffix_array(&self) -> &[usize] {
465        self.tree.suffix_array()
466    }
467
468    pub fn lcp_array(&self) -> &[usize] {
469        self.tree.lcp_array()
470    }
471
472    pub fn rank(&self) -> &[usize] {
473        self.tree.rank()
474    }
475
476    pub fn node_size(&self) -> usize {
477        self.tree.node_size()
478    }

Source

pub fn node(&self, node_id: usize) -> &STNode

Examples found in repository ?

crates/competitive/src/string/suffix_tree.rs (line 446)

425    pub fn new(texts: Vec<Vec<T>>) -> Self {
426        assert!(!texts.is_empty());
427        let total_len: usize = texts.iter().map(|text| text.len() + 1).sum();
428        let mut concat = Vec::with_capacity(total_len - 1);
429        let mut offsets = Vec::with_capacity(texts.len());
430        let mut position_map = Vec::with_capacity(total_len);
431        for (i, text) in texts.iter().enumerate() {
432            offsets.push(concat.len());
433            for (pos, value) in text.iter().cloned().enumerate() {
434                concat.push(Delimited::Value(value));
435                position_map.push((i, pos));
436            }
437            if i + 1 < texts.len() {
438                concat.push(Delimited::Separator(!i));
439            }
440            position_map.push((i, text.len()));
441        }
442
443        let mut tree = SuffixTree::new(concat);
444        for node_id in 0..tree.node_size() {
445            if tree.children(node_id).is_empty() {
446                let node = tree.node(node_id);
447                let (text_idx, pos) = position_map[tree.suffix_array()[node.sa_range.start]];
448                tree.nodes[node_id].depth = texts[text_idx].len() - pos;
449            }
450        }
451
452        Self {
453            texts,
454            offsets,
455            tree,
456            position_map,
457        }
458    }
459
460    pub fn texts(&self) -> &[Vec<T>] {
461        &self.texts
462    }
463
464    pub fn suffix_array(&self) -> &[usize] {
465        self.tree.suffix_array()
466    }
467
468    pub fn lcp_array(&self) -> &[usize] {
469        self.tree.lcp_array()
470    }
471
472    pub fn rank(&self) -> &[usize] {
473        self.tree.rank()
474    }
475
476    pub fn node_size(&self) -> usize {
477        self.tree.node_size()
478    }
479
480    pub fn node(&self, node_id: usize) -> &STNode {
481        self.tree.node(node_id)
482    }
483
484    pub fn children(&self, node_id: usize) -> &[usize] {
485        self.tree.children(node_id)
486    }
487
488    pub fn position_map(&self) -> &[(usize, usize)] {
489        &self.position_map
490    }
491
492    pub fn depth_range(&self, node_id: usize) -> Range<usize> {
493        let node = self.tree.node(node_id);
494        if node.parent == !0 {
495            return 0..0;
496        }
497        let parent_depth = self.tree.node(node.parent).depth;
498        parent_depth + 1..node.depth + 1
499    }

Source

pub fn children(&self, node_id: usize) -> &[usize]

Examples found in repository ?

crates/competitive/src/string/suffix_tree.rs (line 445)

425    pub fn new(texts: Vec<Vec<T>>) -> Self {
426        assert!(!texts.is_empty());
427        let total_len: usize = texts.iter().map(|text| text.len() + 1).sum();
428        let mut concat = Vec::with_capacity(total_len - 1);
429        let mut offsets = Vec::with_capacity(texts.len());
430        let mut position_map = Vec::with_capacity(total_len);
431        for (i, text) in texts.iter().enumerate() {
432            offsets.push(concat.len());
433            for (pos, value) in text.iter().cloned().enumerate() {
434                concat.push(Delimited::Value(value));
435                position_map.push((i, pos));
436            }
437            if i + 1 < texts.len() {
438                concat.push(Delimited::Separator(!i));
439            }
440            position_map.push((i, text.len()));
441        }
442
443        let mut tree = SuffixTree::new(concat);
444        for node_id in 0..tree.node_size() {
445            if tree.children(node_id).is_empty() {
446                let node = tree.node(node_id);
447                let (text_idx, pos) = position_map[tree.suffix_array()[node.sa_range.start]];
448                tree.nodes[node_id].depth = texts[text_idx].len() - pos;
449            }
450        }
451
452        Self {
453            texts,
454            offsets,
455            tree,
456            position_map,
457        }
458    }
459
460    pub fn texts(&self) -> &[Vec<T>] {
461        &self.texts
462    }
463
464    pub fn suffix_array(&self) -> &[usize] {
465        self.tree.suffix_array()
466    }
467
468    pub fn lcp_array(&self) -> &[usize] {
469        self.tree.lcp_array()
470    }
471
472    pub fn rank(&self) -> &[usize] {
473        self.tree.rank()
474    }
475
476    pub fn node_size(&self) -> usize {
477        self.tree.node_size()
478    }
479
480    pub fn node(&self, node_id: usize) -> &STNode {
481        self.tree.node(node_id)
482    }
483
484    pub fn children(&self, node_id: usize) -> &[usize] {
485        self.tree.children(node_id)
486    }

Source

pub fn depth_range(&self, node_id: usize) -> Range<usize>

Source

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

Source

fn node_covering_depth(&self, leaf: usize, depth: usize) -> usize

Examples found in repository ?

crates/competitive/src/string/suffix_tree.rs (line 393)

389    pub fn index_of_distinct_substring(&self, range: Range<usize>) -> u64 {
390        debug_assert!(range.start < range.end && range.end <= self.tree.text.len());
391        let m = range.len();
392        let leaf = self.tree.leafs[self.tree.rank[range.start]];
393        let node = self.tree.node_covering_depth(leaf, m);
394        let offset = m - self.tree.nodes[self.tree.nodes[node].parent].depth - 1;
395        self.prefix_distinct[node - 1] + offset as u64
396    }
397
398    pub fn index_of_substring(&self, range: Range<usize>) -> u64 {
399        debug_assert!(range.start < range.end && range.end <= self.tree.text.len());
400        let m = range.len();
401        let idx = self.tree.rank[range.start];
402        let leaf = self.tree.leafs[idx];
403        let node = self.tree.node_covering_depth(leaf, m);
404        let offset = m - self.tree.nodes[self.tree.nodes[node].parent].depth - 1;
405        let occ = self.tree.nodes[node].sa_range.len() as u64;
406        let occ_idx = (idx - self.tree.nodes[node].sa_range.start) as u64;
407        self.prefix_total[node - 1] + offset as u64 * occ + occ_idx
408    }
409}
410
411pub struct MultipleSuffixTree<T>
412where
413    T: Ord + Clone,
414{
415    texts: Vec<Vec<T>>,
416    offsets: Vec<usize>,
417    tree: SuffixTree<Delimited<T>>,
418    position_map: Vec<(usize, usize)>,
419}
420
421impl<T> MultipleSuffixTree<T>
422where
423    T: Ord + Clone,
424{
425    pub fn new(texts: Vec<Vec<T>>) -> Self {
426        assert!(!texts.is_empty());
427        let total_len: usize = texts.iter().map(|text| text.len() + 1).sum();
428        let mut concat = Vec::with_capacity(total_len - 1);
429        let mut offsets = Vec::with_capacity(texts.len());
430        let mut position_map = Vec::with_capacity(total_len);
431        for (i, text) in texts.iter().enumerate() {
432            offsets.push(concat.len());
433            for (pos, value) in text.iter().cloned().enumerate() {
434                concat.push(Delimited::Value(value));
435                position_map.push((i, pos));
436            }
437            if i + 1 < texts.len() {
438                concat.push(Delimited::Separator(!i));
439            }
440            position_map.push((i, text.len()));
441        }
442
443        let mut tree = SuffixTree::new(concat);
444        for node_id in 0..tree.node_size() {
445            if tree.children(node_id).is_empty() {
446                let node = tree.node(node_id);
447                let (text_idx, pos) = position_map[tree.suffix_array()[node.sa_range.start]];
448                tree.nodes[node_id].depth = texts[text_idx].len() - pos;
449            }
450        }
451
452        Self {
453            texts,
454            offsets,
455            tree,
456            position_map,
457        }
458    }
459
460    pub fn texts(&self) -> &[Vec<T>] {
461        &self.texts
462    }
463
464    pub fn suffix_array(&self) -> &[usize] {
465        self.tree.suffix_array()
466    }
467
468    pub fn lcp_array(&self) -> &[usize] {
469        self.tree.lcp_array()
470    }
471
472    pub fn rank(&self) -> &[usize] {
473        self.tree.rank()
474    }
475
476    pub fn node_size(&self) -> usize {
477        self.tree.node_size()
478    }
479
480    pub fn node(&self, node_id: usize) -> &STNode {
481        self.tree.node(node_id)
482    }
483
484    pub fn children(&self, node_id: usize) -> &[usize] {
485        self.tree.children(node_id)
486    }
487
488    pub fn position_map(&self) -> &[(usize, usize)] {
489        &self.position_map
490    }
491
492    pub fn depth_range(&self, node_id: usize) -> Range<usize> {
493        let node = self.tree.node(node_id);
494        if node.parent == !0 {
495            return 0..0;
496        }
497        let parent_depth = self.tree.node(node.parent).depth;
498        parent_depth + 1..node.depth + 1
499    }
500
501    pub fn kth_substrings(&self) -> MultipleKthSubstrings<'_, T> {
502        MultipleKthSubstrings::new(self)
503    }
504
505    fn to_global_start(&self, text_idx: usize, pos: usize) -> usize {
506        self.offsets[text_idx] + pos
507    }
508}
509
510pub struct MultipleKthSubstrings<'a, T>
511where
512    T: Ord + Clone,
513{
514    tree: &'a MultipleSuffixTree<T>,
515    prefix_distinct: Vec<u64>,
516    prefix_total: Vec<u64>,
517}
518
519impl<'a, T> MultipleKthSubstrings<'a, T>
520where
521    T: Ord + Clone,
522{
523    fn new(tree: &'a MultipleSuffixTree<T>) -> Self {
524        let n = tree.tree.nodes.len();
525        let mut prefix_distinct = vec![0u64; n];
526        let mut prefix_total = vec![0u64; n];
527        for i in 1..n {
528            let node = &tree.tree.nodes[i];
529            let parent_depth = tree.tree.nodes[node.parent].depth;
530            let distinct = (node.depth - parent_depth) as u64;
531            let total = distinct * node.sa_range.len() as u64;
532            prefix_distinct[i] = prefix_distinct[i - 1] + distinct;
533            prefix_total[i] = prefix_total[i - 1] + total;
534        }
535        Self {
536            tree,
537            prefix_distinct,
538            prefix_total,
539        }
540    }
541
542    pub fn kth_distinct_substring(&self, k: u64) -> Option<(usize, Range<usize>)> {
543        let idx = self.prefix_distinct.partition_point(|&x| x <= k);
544        if idx == self.prefix_distinct.len() {
545            return None;
546        }
547        let node = &self.tree.tree.nodes[idx];
548        let parent_depth = self.tree.tree.nodes[node.parent].depth;
549        let offset = k - self.prefix_distinct[idx - 1];
550        let len = parent_depth + 1 + offset as usize;
551        let start = self.tree.tree.suffix_array[node.sa_range.start];
552        let (text_idx, pos) = self.tree.position_map[start];
553        Some((text_idx, pos..pos + len))
554    }
555
556    pub fn kth_substring(&self, k: u64) -> Option<(usize, Range<usize>)> {
557        let idx = self.prefix_total.partition_point(|&x| x <= k);
558        if idx == self.prefix_total.len() {
559            return None;
560        }
561        let node = &self.tree.tree.nodes[idx];
562        let parent_depth = self.tree.tree.nodes[node.parent].depth;
563        let offset = k - self.prefix_total[idx - 1];
564        let occ = node.sa_range.len() as u64;
565        let len_offset = (offset / occ) as usize;
566        let occ_idx = (offset % occ) as usize;
567        let len = parent_depth + 1 + len_offset;
568        let start = self.tree.tree.suffix_array[node.sa_range.start + occ_idx];
569        let (text_idx, pos) = self.tree.position_map[start];
570        Some((text_idx, pos..pos + len))
571    }
572
573    pub fn index_of_distinct_substring(&self, (text_idx, range): (usize, Range<usize>)) -> u64 {
574        debug_assert!(text_idx < self.tree.texts.len());
575        debug_assert!(range.start < range.end && range.end <= self.tree.texts[text_idx].len());
576        let m = range.len();
577        let start = self.tree.to_global_start(text_idx, range.start);
578        let sa_idx = self.tree.tree.rank[start];
579        let leaf = self.tree.tree.leafs[sa_idx];
580        let node = self.tree.tree.node_covering_depth(leaf, m);
581        let parent_depth = self.tree.tree.nodes[self.tree.tree.nodes[node].parent].depth;
582        let offset = m - (parent_depth + 1);
583        self.prefix_distinct[node - 1] + offset as u64
584    }
585
586    pub fn index_of_substring(&self, (text_idx, range): (usize, Range<usize>)) -> u64 {
587        debug_assert!(text_idx < self.tree.texts.len());
588        debug_assert!(range.start < range.end && range.end <= self.tree.texts[text_idx].len());
589        let m = range.len();
590        let start = self.tree.to_global_start(text_idx, range.start);
591        let sa_idx = self.tree.tree.rank[start];
592        let leaf = self.tree.tree.leafs[sa_idx];
593        let node = self.tree.tree.node_covering_depth(leaf, m);
594        let parent_depth = self.tree.tree.nodes[self.tree.tree.nodes[node].parent].depth;
595        let offset = m - (parent_depth + 1);
596        let occ = self.tree.tree.nodes[node].sa_range.len() as u64;
597        let occ_idx = (sa_idx - self.tree.tree.nodes[node].sa_range.start) as u64;
598        self.prefix_total[node - 1] + offset as u64 * occ + occ_idx
599    }