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

//! Suffix array construction and searching algorithms for in-memory binary
//! data, focusing on space efficiency.
//!
//! The suffix array construction algorithm is guaranteed to be O(n) time
//! and O(1) space.
//!
//! For now, This crate uses the Amos Wenger's [C bindings](https://crates.io/crates/cdivsufsort)
//! to Yuta Mori's [dissufsort](https://github.com/y-256/libdivsufsort) to construct suffix array,
//! which is the fastest known suffix array construction algorithm (SACA) running in single thread
//! that uses merely O(1) additional workspace.
//!
//! # Examples
//!
//! Test if the data contains given pattern.
//!
//! ```rust
//! use suffix_array::SuffixArray;
//!
//! let sa = SuffixArray::new(b"splendid splendor");
//! assert!(sa.contains(b"splend"));
//! ```
//!
//! Search for all the occurrences of given pattern in data.
//!
//! ```rust
//! use suffix_array::SuffixArray;
//!
//! let sa = SuffixArray::new(b"splendid splendor");
//! assert_eq!(sa.search_all(b"splend"), &[0, 9]);
//! ```
//!
//! Search for a longest common prefix of given pattern that matches somewhere in the data.
//!
//! ```rust
//! use suffix_array::SuffixArray;
//!
//! let s = b"splendid splendor";
//! let sa = SuffixArray::new(s);
//! let lcp = sa.search_lcp(b"splash");
//! assert_eq!(&s[lcp], b"spl");
//! ```

#[cfg(feature = "pack")]
mod packed_sa;
mod sa;
mod saca;
mod utils;

#[cfg(test)]
mod tests;

pub use self::sa::SuffixArray;
pub use self::saca::MAX_LENGTH;