Crate general_sam
source ·Expand description
This crate provides an implementation of a general suffix automaton.
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
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());
use general_sam::{GeneralSam, BTreeTransTable};
let sam = GeneralSam::<BTreeTransTable<_>>::from_chars("abcbc");
let mut state = sam.get_root_state();
// "b" is not a suffix but at least a substring of "abcbc"
state.feed_chars("b");
assert!(!state.is_accepting());
// "bc" is a suffix of "abcbc"
state.feed_chars("c");
assert!(state.is_accepting());
// "bcbc" is a suffix of "abcbc"
state.feed_chars("bc");
assert!(state.is_accepting());
// "bcbcbc" is not a substring, much less a suffix of "abcbc"
state.feed_chars("bc");
assert!(!state.is_accepting() && state.is_nil());
use general_sam::{GeneralSam, Trie, BTreeTransTable};
let mut trie = Trie::<BTreeTransTable<_>>::default();
trie.insert("hello".chars());
trie.insert("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
Re-exports§
pub use sam::GeneralSam;
pub use sam::GeneralSamNode;
pub use sam::GeneralSamNodeID;
pub use sam::GeneralSamState;
pub use sam::SAM_NIL_NODE_ID;
pub use sam::SAM_ROOT_NODE_ID;
pub use table::BTreeTransTable;
pub use table::BoxBisectTable;
pub use table::ConstructiveTransitionTable;
pub use table::HashTransTable;
pub use table::SmallAlphabet;
pub use table::TransitionTable;
pub use table::VecBisectTable;
pub use table::WholeAlphabetTable;
pub use trie_alike::IterAsChain;
pub use trie_alike::TravelEvent;
pub use trie_alike::TrieNodeAlike;
pub use trie::Trie;
trie
pub use trie::TrieNode;
trie
pub use trie::TrieNodeID;
trie
pub use trie::TrieState;
trie
pub use trie::TRIE_NIL_NODE_ID;
trie
pub use trie::TRIE_ROOT_NODE_ID;
trie
pub use utils::rope;
utils
pub use utils::suffixwise;
utils
pub use utils::tokenize;
utils
pub use utils::tokenize::GreedyTokenizer;
utils