14 releases (5 breaking)

0.6.1 Nov 27, 2023
0.6.0 Nov 27, 2023
0.5.4 Nov 24, 2023
0.4.2 Oct 26, 2023
0.1.1 Oct 13, 2023

#325 in Algorithms

Download history 22/week @ 2023-10-29 350/week @ 2023-11-05 15/week @ 2023-11-12 60/week @ 2023-11-19 298/week @ 2023-11-26 38/week @ 2023-12-03 34/week @ 2023-12-10 34/week @ 2023-12-17 31/week @ 2023-12-24 18/week @ 2023-12-31 4/week @ 2024-01-07 5/week @ 2024-01-14 21/week @ 2024-01-21 59/week @ 2024-01-28 17/week @ 2024-02-04 72/week @ 2024-02-11

169 downloads per month

MIT/Apache

94KB
2.5K SLoC

general-sam

Crates.io Docs.rs License Build status

A general suffix automaton implementation in Rust.

Python bindings and some utilities are also available. Please check out general-sam-py.

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".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());
// NOTE: This example requires the `trie` feature.
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

License

This project is licensed under either of

at your option.

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

Dependencies

~75KB