Crate suffix_automaton 

Suffix Automaton (SAM).

A suffix automaton is a directed acyclic automaton that recognises exactly the set of substrings of a given string. It has at most 2n - 1 states for an input of length n, and every state corresponds to a distinct set of end positions in the original string — hence to a distinct set of substrings.

Once built, you can answer:

• Is p a substring of s? (O(|p|))
• How many distinct substrings does s have? (sum over states of len(state) - len(link(state)))
• Number of occurrences of a pattern (when state.occ is computed)
• Longest common substring between two strings

Example

use suffix_automaton::SuffixAutomaton;

let mut sam = SuffixAutomaton::new();
for ch in "ababa".chars() {
    sam.extend(ch);
}
assert!(sam.contains("aba"));
assert!(sam.contains("bab"));
assert!(!sam.contains("bb"));

Structs

State

State of a suffix automaton.

SuffixAutomaton

Suffix Automaton over a sequence of chars.