general-sam
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 ;
let sam = from_bytes;
// "cbc" is a suffix of "abcbc"
assert!;
// "bcb" is not a suffix of "abcbc"
assert!;
use ;
let sam = from_chars;
let mut state = sam.get_root_state;
// "b" is not a suffix but at least a substring of "abcbc"
state.feed_chars;
assert!;
// "bc" is a suffix of "abcbc"
state.feed_chars;
assert!;
// "bcbc" is a suffix of "abcbc"
state.feed_chars;
assert!;
// "bcbcbc" is not a substring, much less a suffix of "abcbc"
state.feed_chars;
assert!;
#
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
at your option.
The SPDX license identifier for this project is MIT OR Apache-2.0
.