general-sam

A general suffix automaton implementation in Rust.

Python bindings and some utilities are also available. Please check out pybind.

The suffix automaton of abcbc, image from 后缀自动机 - OI Wiki.

Examples

use general_sam::sam::GeneralSAM;

let sam = GeneralSAM::construct_from_bytes("abcbc");
// => GeneralSAM<u8>

assert!(sam.get_root_state().feed_bytes("cbc").is_accepting());
assert!(!sam.get_root_state().feed_bytes("bcb").is_accepting());

use general_sam::sam::GeneralSAM;

let sam = GeneralSAM::construct_from_chars("abcbc".chars());
// => GeneralSAM<char>

let state = sam.get_root_state();
let state = state.feed_chars("b");
assert!(!state.is_accepting());
let state = state.feed_chars("c");
assert!(state.is_accepting());
let state = state.feed_chars("bc");
assert!(state.is_accepting());
let state = state.feed_chars("bc");
assert!(!state.is_accepting() && state.is_nil());

use general_sam::{sam::GeneralSAM, trie::Trie};

let mut trie = Trie::default();
trie.insert_iter("hello".chars());
trie.insert_iter("Chielo".chars());

let sam: GeneralSAM<char> = GeneralSAM::construct_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

License

• © 2023 Chielo Newctle <ChieloNewctle@gmail.com>
• © 2023 ModelTC Team

This project is licensed under either of

• Apache License, Version 2.0 (LICENSE-APACHE)
• MIT license (LICENSE-MIT)

at your option.

The SPDX license identifier for this project is MIT OR Apache-2.0.