strings.suffix_automaton
========================

.. py:module:: strings.suffix_automaton

.. autoapi-nested-parse::

   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
-------

.. autoapisummary::

   strings.suffix_automaton.State
   strings.suffix_automaton.SuffixAutomaton


Module Contents
---------------

.. py:class:: State

   State (node) in a Suffix Automaton.


   .. py:attribute:: length
      :type:  int
      :value: 0



   .. py:attribute:: link
      :type:  int
      :value: -1



   .. py:attribute:: next
      :type:  dict[str, int]


.. py:class:: 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.


   .. py:method:: 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



   .. py:method:: 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



   .. py:method:: 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



   .. py:method:: extend(char: str) -> None

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



   .. py:attribute:: last
      :type:  int
      :value: 0



   .. py:attribute:: states
      :type:  list[State]


   .. py:attribute:: string
      :type:  str