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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

//! This crate provides an implementation of a general suffix automaton.
//!
//! ```mermaid
//! flowchart LR
//!   init((ε))
//!   a((a))
//!   b((b))
//!   ab((ab))
//!   bc(((bc)))
//!   abc((abc))
//!   abcb((abcb))
//!   abcbc(((abcbc)))
//!
//!   init -- a --> a
//!   init -- b --> b
//!   a -- b --> ab
//!   b -- c --> bc
//!   init -- c --> bc
//!   ab -- c --> abc
//!   bc -- b --> abcb
//!   abc -- b --> abcb
//!   abcb -- c --> abcbc
//! ```
//!
//! > The suffix automaton of abcbc.
//!
//! # Examples
//!
//! ```rust
//! use general_sam::{GeneralSAM, BTreeTransTable};
//!
//! let sam = GeneralSAM::<BTreeTransTable<_>>::from_bytes("abcbc");
//!
//! // "cbc" is a suffix of "abcbc"
//! assert!(sam.get_root_state().feed_bytes("cbc").is_accepting());
//!
//! // "bcb" is not a suffix of "abcbc"
//! assert!(!sam.get_root_state().feed_bytes("bcb").is_accepting());
//! ```
//!
//! ```rust
//! use general_sam::{GeneralSAM, BTreeTransTable};
//!
//! let sam = GeneralSAM::<BTreeTransTable<_>>::from_chars("abcbc".chars());
//!
//! let state = sam.get_root_state();
//!
//! // "b" is not a suffix but at least a substring of "abcbc"
//! let state = state.feed_chars("b");
//! assert!(!state.is_accepting());
//!
//! // "bc" is a suffix of "abcbc"
//! let state = state.feed_chars("c");
//! assert!(state.is_accepting());
//!
//! // "bcbc" is a suffix of "abcbc"
//! let state = state.feed_chars("bc");
//! assert!(state.is_accepting());
//!
//! // "bcbcbc" is not a substring, much less a suffix of "abcbc"
//! let state = state.feed_chars("bc");
//! assert!(!state.is_accepting() && state.is_nil());
//! ```
//!
//! ```rust
//! # #[cfg(feature = "trie")] {
//! use general_sam::{GeneralSAM, Trie, BTreeTransTable};
//!
//! let mut trie = Trie::<BTreeTransTable<_>>::default();
//! trie.insert_iter("hello".chars());
//! trie.insert_iter("Chielo".chars());
//!
//! let sam = GeneralSAM::<BTreeTransTable<_>>::from_trie(trie.get_root_state());
//!
//! assert!(sam.get_root_state().feed_chars("lo").is_accepting());
//! assert!(sam.get_root_state().feed_chars("ello").is_accepting());
//! assert!(sam.get_root_state().feed_chars("elo").is_accepting());
//!
//! assert!(!sam.get_root_state().feed_chars("el").is_accepting());
//! assert!(!sam.get_root_state().feed_chars("el").is_nil());
//!
//! assert!(!sam.get_root_state().feed_chars("bye").is_accepting());
//! assert!(sam.get_root_state().feed_chars("bye").is_nil());
//! # }
//! ```
//!
//! # References
//!
//! - [Mehryar Mohri, Pedro Moreno, Eugene Weinstein.
//!   General suffix automaton construction algorithm and space bounds.][paper]
//! - 刘研绎《后缀自动机在字典树上的拓展》
//! - [广义后缀自动机 - OI Wiki][general-sam-oi-wiki]
//!
//! [paper]: https://doi.org/10.1016/j.tcs.2009.03.034
//! [general-sam-oi-wiki]: https://oi-wiki.org/string/general-sam/
#![cfg_attr(doc_cfg, feature(doc_cfg))]

pub mod sam;
pub mod table;
pub mod trie_alike;

pub use {
    sam::{
        GeneralSAM, GeneralSAMNode, GeneralSAMNodeID, GeneralSAMState, SAM_NIL_NODE_ID,
        SAM_ROOT_NODE_ID,
    },
    table::{BTreeTransTable, ConstructiveTransitionTable, TransitionTable},
    trie_alike::{IterAsChain, TravelEvent, TrieNodeAlike},
};

#[cfg(feature = "trie")]
#[cfg_attr(doc_cfg, doc(cfg(feature = "trie")))]
pub mod trie;
#[cfg(feature = "trie")]
#[cfg_attr(doc_cfg, doc(cfg(feature = "trie")))]
pub use trie::{Trie, TrieNode, TrieNodeID, TrieState, TRIE_NIL_NODE_ID, TRIE_ROOT_NODE_ID};

#[cfg(feature = "utils")]
#[cfg_attr(doc_cfg, doc(cfg(feature = "utils")))]
pub mod utils;
#[cfg(feature = "utils")]
#[cfg_attr(doc_cfg, doc(cfg(feature = "utils")))]
pub use utils::{rope, suffixwise, tokenize};

#[cfg(test)]
mod tests;