Suffix automaton (SAM) over byte alphabet. More...

#include <Suffix_Structures.H>

Collaboration diagram for Aleph::Suffix_Automaton:

Classes
struct	State
	One automaton state. More...

Public Member Functions
	Suffix_Automaton ()
	Construct an empty suffix automaton (SAM) with only the root state.

void	clear ()
	Reset the automaton to its initial empty state (root only).

void	extend (const char ch)
	Extend the SAM with a single character.

void	build (const std::string_view text)
	Build the SAM from an entire string.

bool	contains (const std::string_view pattern) const
	Return true if `pattern` is a substring of the built text.

size_t	distinct_substring_count () const
	Count the number of distinct substrings in the built text.

std::string	longest_common_substring (const std::string_view other) const
	Find the longest common substring between the built SAM text and `other`.

size_t	state_count () const noexcept
	Return the number of states in the SAM.

const Array< State > &	states () const noexcept
	Access the internal states array for testing/inspection.

Private Member Functions
void	mark_terminals ()
	Traverse suffix links from last and mark all states as terminal.

Private Attributes
Array< State >	states_

int	last_ = 0

Detailed Description

Suffix automaton (SAM) over byte alphabet.

Supports substring checks, distinct substring counting, and longest common substring against another string.

Examples: suffix_automaton_example.cc.

Definition at line 586 of file Suffix_Structures.H.

Constructor & Destructor Documentation

◆ Suffix_Automaton()

Aleph::Suffix_Automaton::Suffix_Automaton ( )

inline

Construct an empty suffix automaton (SAM) with only the root state.

Exceptions

None.

Complexity: O(1).

Definition at line 627 of file Suffix_Structures.H.

References clear().

Member Function Documentation

◆ build()

void Aleph::Suffix_Automaton::build ( const std::string_view text )

inline

Build the SAM from an entire string.

Parameters

[in] text The input string to process.

Exceptions

None.

Complexity: O(n) where n is text.size().

Examples: suffix_automaton_example.cc.

Definition at line 711 of file Suffix_Structures.H.

References clear(), Aleph::divide_and_conquer_partition_dp(), extend(), and mark_terminals().

Referenced by Aleph::longest_common_substring_sam(), main(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ clear()

void Aleph::Suffix_Automaton::clear ( )

inline

Reset the automaton to its initial empty state (root only).

Exceptions

None.

Complexity: O(1).

Definition at line 637 of file Suffix_Structures.H.

References last_, and states_.

Referenced by Suffix_Automaton(), and build().

◆ contains()

bool Aleph::Suffix_Automaton::contains ( const std::string_view pattern ) const

inline

Return true if pattern is a substring of the built text.

Parameters

[in] pattern The substring pattern to search for.

Returns: True if the SAM contains pattern, false otherwise.

Exceptions

None.

Complexity: O(m) where m is pattern.size().

Examples: suffix_automaton_example.cc.

Definition at line 727 of file Suffix_Structures.H.

References Aleph::next(), and states_.

◆ distinct_substring_count()

size_t Aleph::Suffix_Automaton::distinct_substring_count ( ) const

inline

Count the number of distinct substrings in the built text.

Returns: The total count of unique substrings.

Exceptions

None.

Complexity: O(V) where V is the number of states.

Examples: suffix_automaton_example.cc.

Definition at line 746 of file Suffix_Structures.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Suffix_Automaton::State::len, Aleph::Suffix_Automaton::State::link, and states_.

◆ extend()

void Aleph::Suffix_Automaton::extend ( const char ch )

inline

Extend the SAM with a single character.

Parameters

[in] ch The character to append to the current text representation.

Exceptions

None.

Complexity: Amortized O(1).

Definition at line 654 of file Suffix_Structures.H.

References Aleph::and, Aleph::divide_and_conquer_partition_dp(), last_, Aleph::Suffix_Automaton::State::len, Aleph::next(), and states_.

Referenced by build().

◆ longest_common_substring()

std::string Aleph::Suffix_Automaton::longest_common_substring ( const std::string_view other ) const

inline

Find the longest common substring between the built SAM text and other.

Parameters

[in] other String to compare against the built SAM text.

Returns: The longest common substring. Returns an empty string if no common substring exists.

Exceptions

None.

Complexity: O(m) where m is other.size().

Examples: suffix_automaton_example.cc.

Definition at line 767 of file Suffix_Structures.H.

References Aleph::and, Aleph::divide_and_conquer_partition_dp(), Aleph::next(), and states_.

◆ mark_terminals()

void Aleph::Suffix_Automaton::mark_terminals ( )

inlineprivate

Traverse suffix links from last and mark all states as terminal.

Exceptions

None.

Definition at line 611 of file Suffix_Structures.H.

References last_, and states_.

Referenced by build().

◆ state_count()

size_t Aleph::Suffix_Automaton::state_count ( ) const

inlinenoexcept

Return the number of states in the SAM.

Returns: The size of the internal states array.

Exceptions

None.

Complexity: O(1).

Examples: suffix_automaton_example.cc.

Definition at line 815 of file Suffix_Structures.H.

References states_.

◆ states()

const Array< State > & Aleph::Suffix_Automaton::states ( ) const

inlinenoexcept

Access the internal states array for testing/inspection.

Returns: A constant reference to the underlying Array of states.

Exceptions

None.

Complexity: O(1).

Definition at line 826 of file Suffix_Structures.H.

References states_.

Member Data Documentation

◆ last_

int Aleph::Suffix_Automaton::last_ = 0

private

Definition at line 606 of file Suffix_Structures.H.

Referenced by clear(), extend(), and mark_terminals().

◆ states_

Array<State> Aleph::Suffix_Automaton::states_

private

Definition at line 605 of file Suffix_Structures.H.

Referenced by clear(), contains(), distinct_substring_count(), extend(), longest_common_substring(), mark_terminals(), state_count(), and states().

The documentation for this class was generated from the following file:

Suffix_Structures.H

Classes

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ Suffix_Automaton()

Member Function Documentation

◆ build()

◆ clear()

◆ contains()

◆ distinct_substring_count()

◆ extend()

◆ longest_common_substring()

◆ mark_terminals()

◆ state_count()

◆ states()

Member Data Documentation

◆ last_

◆ states_