Class SuffixAutomaton

Class Documentation

class SuffixAutomaton

the suffix automaton of a string, built a byte at a time

Public Functions

SuffixAutomaton(void)

the automaton of the empty string

explicit SuffixAutomaton(std::string_view S)

the automaton of S

void extend(unsigned char c)

the automaton of S c from that of S

Post:

at most 2 |S c| states (an invariant)

bool contains(std::string_view P) const

P is a substring of S.

std::size_t occurrences(std::string_view P) const

the number of the occurrences of P in S (n + 1 for the empty P)

std::size_t distinctSubstrings(void) const

the number of the nonempty distinct substrings of S

std::pair<std::size_t, std::size_t> longestCommonSubstring(std::string_view T) const

the length of a longest common substring of S and T, and where it ends in T (one past its last byte), the first one in T

inline std::size_t states(void) const

the number of states

inline std::size_t size(void) const

the length of S