strings.suffix_automaton

Suffix Automaton (SAM) for String Processing.

Reference: https://en.wikipedia.org/wiki/Suffix_automaton Reference: https://cp-algorithms.com/string/suffix-automaton.html

A Suffix Automaton is the minimal Deterministic Finite Automaton (DFA) that recognizes all suffixes (and substrings) of a given string in O(N) time and O(N) space.

Classes

State	State (node) in a Suffix Automaton.
SuffixAutomaton	Suffix Automaton data structure.

Module Contents

class strings.suffix_automaton.State

State (node) in a Suffix Automaton.

length: int = 0

link: int = -1

next: dict[str, int]

class strings.suffix_automaton.SuffixAutomaton(string: str)

Suffix Automaton data structure.

>>> sam = SuffixAutomaton("abacaba")
>>> sam.contains("abac")
True
>>> sam.contains("caba")
True
>>> sam.contains("xyz")
False
>>> sam.count_distinct_substrings()
21
>>> sam.count_occurrences("aba")
2
>>> sam.count_occurrences("a")
4
>>> SuffixAutomaton("")
Traceback (most recent call last):
    ...
ValueError: Input string must not be empty.

contains(pattern: str) → bool

Check if pattern exists as a substring in O(|pattern|) time.

>>> sam = SuffixAutomaton("banana")
>>> sam.contains("nan")
True
>>> sam.contains("apple")
False

count_distinct_substrings() → int

Compute total number of distinct substrings in O(N) time.

>>> sam = SuffixAutomaton("abc")
>>> sam.count_distinct_substrings()
6
>>> SuffixAutomaton("aaaa").count_distinct_substrings()
4

count_occurrences(pattern: str) → int

Count occurrences of pattern as a substring in the text in O(N + |pattern|) time

>>> sam = SuffixAutomaton("banana")
>>> sam.count_occurrences("an")
2
>>> sam.count_occurrences("na")
2
>>> sam.count_occurrences("banana")
1
>>> sam.count_occurrences("xyz")
0

extend(char: str) → None

Extend the Suffix Automaton by appending character char. Time Complexity: O(1) amortized

last: int = 0

states: list[State]

string: str