Crate general_sam

source ·
Expand description

This crate provides an implementation of a general suffix automaton.

the suffix automaton of abcbc
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

Modules