File SuffixAutomaton.h

↰ Parent directory (ADS/string)

The suffix automaton (the directed acyclic word graph, DAWG) of a string S of n bytes, beyond the book: the smallest deterministic automaton that accepts the suffixes of S, whose paths from the start spell exactly the substrings of S.

Definition (ADS/string/SuffixAutomaton.h)

Detailed Description

Its states are the classes of the substrings by their sets of end places, :math:`[

mathrm{endpos}( u ) = { j : S[ j - |u| + 1 .. j ] = u } ,

` a class holding the suffixes of its longest member of lengths :math:` ( mathit{len}( mathit{link}( v ) ) , mathit{len}( v ) ] , where the suffix link of v is the class of the longest suffix in another class. It has at most :math: 2 n - 1 ` states (n at least 2) and :math:` 3 n - 4 ` transitions (n at least 3), and the construction of Blumer et al. adds the bytes one at a time: the new state of :math:` S c ` gets the transitions on c from the suffix path of the last state, which stops at the first state p that has one; if it leads to q with :math:` mathit{len}( q ) = mathit{len}( p ) + 1 , q is the new link, otherwise q is cloned with that length, O( n ) amortized time for a constant alphabet. Here the transitions of a state are a short vector of ( byte , state ) pairs, searched linearly, so that the time is :math: O( n sigma ) ` for :math:` sigma ` distinct bytes.

  • contains( P ) follows P from the start, O( |P| sigma );

  • occurrences( P ) is the size of the end set of the state of P, counted once for all by adding the count of each state (1 if it ends a prefix of S, 0 for a clone) to its link, in decreasing order of the lengths;

  • distinctSubstrings() is :math:` sum_{v ne mathit{start}} ( mathit{len}( v ) - mathit{len}( mathit{link}( v ) ) ) `, the number of nonempty distinct substrings of S;

  • longestCommonSubstring( T ) scans T keeping the longest suffix of :math:` T[ 0 .. j ] ` that is a substring of S, following the links on a mismatch, O( |T| sigma ).

The contracts [see File Contract.h]: at most 2 n states (an invariant), and the results equal those of the definitions on the substrings (the audits of the tests). The functions are defined in SuffixAutomaton.tpp.

  1. Blumer, J. Blumer, D. Haussler, A. Ehrenfeucht, M. T. Chen, J. Seiferas, The smallest automaton recognizing the subwords of a text, Theoretical Computer Science 40, 31-55, 1985, doi:10.1016/0304-3975(85)90157-4

  1. Crochemore, Transducers and repetitions, Theoretical Computer Science 45, 63-86, 1986, doi:10.1016/0304-3975(86)90041-1

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

  • ADS/Contract.h (File Contract.h)

  • ADS/string/impl/SuffixAutomaton.tpp

  • cstddef

  • cstdint

  • string_view

  • utility

  • vector

Namespaces

Classes