1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109

//! no_std support

//! # Suffix Array
//! Implementation of the [suffix array](https://www.researchgate.net/profile/Daricks_Wai_Hong_Chan/publication/221577802_Linear_Suffix_Array_Construction_by_Almost_Pure_Induced-Sorting/links/00b495318a21ba484f000000/Linear-Suffix-Array-Construction-by-Almost-Pure-Induced-Sorting.pdf?origin=publication_detail)
//! construction of which is performed in linear time
//!
//! ## Examples
//!
//! ```
//! use suff_collections::{array::*, tree::*, lcp::*};
//!
//! // let word = "Some word";
//! let word: &str = "Some word\0";
//! let find: &str = "word";
//!
//! // construct suffix array
//! // let sa = SuffixArray::<usize>::new_stack(word);
//! // let sa = SuffixArray::<u8>::new(word);
//! // let sa = SuffixArray::<u16>::new(word);
//! // let sa = SuffixArray::<u32>::new(word);
//! let sa = SuffixArray::<usize>::new(word);
//!
//! // construct lcp
//! // lcp[i] = max_pref(sa[i], sa[i - 1]) && lcp.len() == sa.len()
//! let lcp: LCP<usize> = sa.lcp();
//!
//! // finds the entry position of the line 'find' in 'word'
//! // O(|find| * log(|word|))
//! let res: Option<usize> = sa.find(find);
//!
//! // finds all the entry position of the line 'find' in 'word'
//! // O(|find| * log(|word|))
//! let res_all: &[usize] = sa.find_all(find);
//!
//! // finds the entry position of the line 'find' in 'word'
//! // O(|word|)
//! let res: Option<usize> = sa.find_big(&sa.lcp(), find);
//!
//! // finds all the entry position of the line 'find' in 'word'
//! // O(|word|)
//! let res_all: &[usize] = sa.find_all_big(&sa.lcp(), find);
//!
//! // convert suffix array to suffix tree
//! let st = SuffixTree::from(sa);
//! ```

//! # Suffix Tree
//! Implementation of the [suffix tree](https://web.stanford.edu/~mjkay/gusfield.pdf)
//! construction of which is performed in linear time
//!
//! ## Examples
//!
//! ```
//! use suff_collections::{array::*, tree::*, lcp::*};
//!
//! // let word = "Some word";
//! let word: &str = "Some word\0";
//! let find: &str = "word";
//!
//! // construct suffix tree
//! let st: SuffixTree = SuffixTree::new(word);
//!
//! // finds the entry position of the line 'find' in 'word'
//! let res: Option<usize> = st.find(find);
//!
//! // construct lcp
//! // lcp[i] = max_pref(sa[i], sa[i - 1]) && lcp.len() == sa.len()
//! // let lcp: LCP<u8> = st.lcp::<u8>();
//! // let lcp: LCP<u16> = st.lcp::<u16>();
//! // let lcp: LCP<u32> = st.lcp::<u32>();
//! let lcp: LCP<usize> = st.lcp::<usize>();
//!
//! // convert suffix tree to suffix array
//! // let sa = SuffixArray::<u8>::from(st);
//! // let sa = SuffixArray::<u16>::from(st);
//! // let sa = SuffixArray::<u32>::from(st);
//! let sa = SuffixArray::<usize>::from(st);
//! ```

#![no_std]
#[macro_use(vec)]
extern crate alloc;
pub mod array;
pub mod lcp;
pub mod tree;

pub(crate) mod bit;

use alloc::borrow::{Cow, ToOwned};
use alloc::vec::Vec;
use core::str;
fn canonic_word(word: &str) -> Cow<'_, str> {
    if word.as_bytes().last() == Some(&0) {
        Cow::from(word)
    } else {
        Cow::from(
            str::from_utf8(
                &word
                    .as_bytes()
                    .iter()
                    .chain(&[0])
                    .copied()
                    .collect::<Vec<_>>(),
            )
            .unwrap()
            .to_owned(),
        )
    }
}