Naive compressed suffix tree (didactic implementation). More...

#include <Suffix_Structures.H>

Collaboration diagram for Aleph::Naive_Suffix_Tree:

Classes
struct	Node
	One tree node. More...

Public Member Functions
	Naive_Suffix_Tree (const std::string_view text="")
	Construct a naive suffix tree.

void	build (const std::string_view text)
	Build or rebuild the suffix tree for `text`.

bool	contains (const std::string_view pattern) const
	Return true if the pattern appears in the text.

Array< size_t >	find_all (const std::string_view pattern) const
	Return all occurrences of a pattern.

size_t	node_count () const noexcept
	Return the number of nodes in the tree.

size_t	text_size () const noexcept
	Return the text size (without terminal marker).

const Array< Node > &	nodes () const noexcept
	Return the internal node array for inspection/debugging.

Static Public Attributes
static constexpr size_t	npos = std::numeric_limits<size_t>::max()

Private Member Functions
size_t	create_node (const size_t start, const size_t end, const size_t parent, const size_t suffix_index)

size_t	find_child_by_first_char (const size_t node, const char c) const

void	replace_child (const size_t parent, const size_t old_child, const size_t new_child)

void	insert_suffix (const size_t suffix_start)

void	collect_leaf_suffixes (const size_t node, Array< size_t > &out) const

Static Private Member Functions
static char	choose_terminal (const std::string_view s)

Private Attributes
std::string	text_

size_t	original_size_ = 0

Array< Node >	nodes_

Detailed Description

Naive compressed suffix tree (didactic implementation).

This is intentionally simple and educational (O(n^2) construction), not Ukkonen's linear-time algorithm.

Note: Construction is O(n^2) in time and space. This class is meant for teaching and small inputs; for production use prefer the suffix array + LCP approach or an external linear-time library.; A unique terminal byte is appended internally via choose_terminal(). If every byte value (0–255) appears in the input, construction will throw std::domain_error.

Examples: suffix_tree_example.cc.

Definition at line 252 of file Suffix_Structures.H.

Constructor & Destructor Documentation

◆ Naive_Suffix_Tree()

Aleph::Naive_Suffix_Tree::Naive_Suffix_Tree ( const std::string_view text = "" )

inlineexplicit

Construct a naive suffix tree.

Parameters

[in] text The text to build the tree from. If empty, the tree will only contain the terminal character.

Exceptions

std::domain_error If all 256 byte values are present in text, leaving no unique sentinel character available.

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

Definition at line 412 of file Suffix_Structures.H.

References build(), and Aleph::divide_and_conquer_partition_dp().

Member Function Documentation

◆ build()

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

inline

Build or rebuild the suffix tree for text.

Parameters

[in] text The text to build the tree from.

Exceptions

std::domain_error If all 256 byte values are present in text, leaving no unique sentinel character available.

Complexity: O(n^2) time and O(n^2) space in the worst case, where n is text.size().

Definition at line 424 of file Suffix_Structures.H.

References choose_terminal(), Aleph::divide_and_conquer_partition_dp(), insert_suffix(), nodes_, original_size_, and text_.

Referenced by Naive_Suffix_Tree().

◆ choose_terminal()

static char Aleph::Naive_Suffix_Tree::choose_terminal ( const std::string_view s )

inlinestaticprivate

Definition at line 275 of file Suffix_Structures.H.

References ah_domain_error, and Aleph::divide_and_conquer_partition_dp().

Referenced by build().

◆ collect_leaf_suffixes()

void Aleph::Naive_Suffix_Tree::collect_leaf_suffixes	(	const size_t	node,
		Array< size_t > &	out
	)		const

inlineprivate

Definition at line 382 of file Suffix_Structures.H.

References Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::Array< T >::is_empty(), nodes_, npos, original_size_, and Aleph::Array< T >::remove_last().

Referenced by find_all().

◆ contains()

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

inline

Return true if the pattern appears in the text.

Parameters

[in] pattern The substring pattern to search for.

Returns: True if pattern is found in the text, false otherwise. If pattern is empty, returns true.

Exceptions

None.

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

Definition at line 448 of file Suffix_Structures.H.

References Aleph::and, Aleph::divide_and_conquer_partition_dp(), find_child_by_first_char(), k, nodes_, npos, and text_.

Referenced by TEST(), TEST(), TEST(), and TEST().

◆ create_node()

size_t Aleph::Naive_Suffix_Tree::create_node	(	const size_t	start,
		const size_t	end,
		const size_t	parent,
		const size_t	suffix_index
	)

inlineprivate

Definition at line 293 of file Suffix_Structures.H.

References Aleph::Naive_Suffix_Tree::Node::end, nodes_, Aleph::Naive_Suffix_Tree::Node::parent, Aleph::Naive_Suffix_Tree::Node::start, and Aleph::Naive_Suffix_Tree::Node::suffix_index.

Referenced by insert_suffix().

◆ find_all()

Array< size_t > Aleph::Naive_Suffix_Tree::find_all ( const std::string_view pattern ) const

inline

Return all occurrences of a pattern.

Parameters

[in] pattern The substring pattern to search for.

Returns: An array containing the starting positions of all occurrences of pattern in the text, sorted in ascending order. Returns an empty array if no occurrences are found.

Note: If pattern is empty, all positions [0, text.size()] are returned.

Exceptions

None.

Complexity: O(m + k log k) where m is pattern.size() and k is the number of occurrences.

Examples: suffix_tree_example.cc.

Definition at line 500 of file Suffix_Structures.H.

References Aleph::suffix_structures_detail::all_positions(), Aleph::and, collect_leaf_suffixes(), Aleph::divide_and_conquer_partition_dp(), find_child_by_first_char(), k, nodes_, npos, original_size_, Aleph::suffix_structures_detail::sort_matches(), and text_.

Referenced by main(), TEST(), TEST(), TEST(), and TEST().

◆ find_child_by_first_char()

size_t Aleph::Naive_Suffix_Tree::find_child_by_first_char	(	const size_t	node,
		const char	c
	)		const

inlineprivate

Definition at line 307 of file Suffix_Structures.H.

References nodes_, npos, Aleph::Array< T >::size(), and text_.

Referenced by contains(), find_all(), and insert_suffix().

◆ insert_suffix()

void Aleph::Naive_Suffix_Tree::insert_suffix ( const size_t suffix_start )

inlineprivate

Definition at line 330 of file Suffix_Structures.H.

References Aleph::and, create_node(), Aleph::divide_and_conquer_partition_dp(), find_child_by_first_char(), k, nodes_, npos, replace_child(), Aleph::split(), and text_.

Referenced by build().

◆ node_count()

size_t Aleph::Naive_Suffix_Tree::node_count ( ) const

inlinenoexcept

Return the number of nodes in the tree.

Returns: Total number of nodes (internal and leaves).

Exceptions

None.

Complexity: O(1).

Examples: suffix_tree_example.cc.

Definition at line 551 of file Suffix_Structures.H.

References nodes_.

Referenced by main(), and TEST().

◆ nodes()

const Array< Node > & Aleph::Naive_Suffix_Tree::nodes ( ) const

inlinenoexcept

Return the internal node array for inspection/debugging.

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

Exceptions

None.

Complexity: O(1).

Definition at line 574 of file Suffix_Structures.H.

References nodes_.

Referenced by TEST().

◆ replace_child()

void Aleph::Naive_Suffix_Tree::replace_child	(	const size_t	parent,
		const size_t	old_child,
		const size_t	new_child
	)

inlineprivate

Definition at line 318 of file Suffix_Structures.H.

References Aleph::divide_and_conquer_partition_dp(), and nodes_.

Referenced by insert_suffix().

◆ text_size()

size_t Aleph::Naive_Suffix_Tree::text_size ( ) const

inlinenoexcept

Return the text size (without terminal marker).

Returns: The size of the original text used to build the tree. This corresponds to the original_size_ member.

Exceptions

None.

Complexity: O(1).

Definition at line 563 of file Suffix_Structures.H.

References original_size_.

Referenced by TEST().

Member Data Documentation

◆ nodes_

Array<Node> Aleph::Naive_Suffix_Tree::nodes_

private

Definition at line 273 of file Suffix_Structures.H.

Referenced by build(), collect_leaf_suffixes(), contains(), create_node(), find_all(), find_child_by_first_char(), insert_suffix(), node_count(), nodes(), and replace_child().

◆ npos

constexpr size_t Aleph::Naive_Suffix_Tree::npos = std::numeric_limits<size_t>::max()

staticconstexpr

Definition at line 255 of file Suffix_Structures.H.

Referenced by collect_leaf_suffixes(), contains(), find_all(), find_child_by_first_char(), and insert_suffix().

◆ original_size_

size_t Aleph::Naive_Suffix_Tree::original_size_ = 0

private

Definition at line 272 of file Suffix_Structures.H.

Referenced by build(), collect_leaf_suffixes(), find_all(), and text_size().

◆ text_

std::string Aleph::Naive_Suffix_Tree::text_

private

Definition at line 271 of file Suffix_Structures.H.

Referenced by build(), contains(), find_all(), find_child_by_first_char(), and insert_suffix().

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

Suffix_Structures.H

Classes

Public Member Functions

Static Public Attributes

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ Naive_Suffix_Tree()

Member Function Documentation

◆ build()

◆ choose_terminal()

◆ collect_leaf_suffixes()

◆ contains()

◆ create_node()

◆ find_all()

◆ find_child_by_first_char()

◆ insert_suffix()

◆ node_count()

◆ nodes()

◆ replace_child()

◆ text_size()

Member Data Documentation

◆ nodes_

◆ npos

◆ original_size_

◆ text_