Crate general_sam

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

• Mehryar Mohri, Pedro Moreno, Eugene Weinstein. General suffix automaton construction algorithm and space bounds.
• 刘研绎《后缀自动机在字典树上的拓展》
• 广义后缀自动机 - OI Wiki

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

Modules

• sam
  A general suffix automaton implementation.
• table
  Transition table backends.
• trietrie
  Trie, supporting TrieNodeAlike.
• trie_alike
  A trait for constructing GeneralSam from structures that form a trie, and some utilities to construct GeneralSam from iterators.
• utilsutils