step20 Namespace Reference

Namespaces
namespace	edit_distance
namespace	least_frequently_used
namespace	least_recently_used
namespace	longest_common_subsequence
namespace	longest_common_substring
namespace	substring_search

Classes
class	enhanced_suffix_array
	Kasai's algorithm for constructing longest common prefix array. More...
struct	generator
class	suffix_array
	Manber's algorithm for constructing sorted array of non-empty suffixes. More...
class	suffix_tree
	Ukkonen's online algorithm for constructing suffix tree. More...

Functions
template<class... Ts>
auto	longest_repeated_substring (const enhanced_suffix_array< Ts... > &arr) -> std::basic_string_view< typename enhanced_suffix_array< Ts... >::value_type >
	Find the longest substring that occurs at least twice.
template<class... Ts>
auto	longest_repeated_substring (const suffix_tree< Ts... > &tree) -> std::basic_string_view< typename suffix_tree< Ts... >::value_type >
	Find the longest substring that occurs at least twice.
template<std::ranges::input_range R, class Compare = std::less<>>
	suffix_array (R, Compare={}) -> suffix_array< std::ranges::range_value_t< R >, std::size_t, Compare >
template<std::ranges::input_range R, class Compare = std::less<>>
	enhanced_suffix_array (R, Compare={}) -> enhanced_suffix_array< std::ranges::range_value_t< R >, std::size_t, Compare >
template<class To , std::ranges::input_range From>
To	to (From &&from)
template<template< class... > class To, std::ranges::input_range From>
auto	to (From &&from)

Variables
auto	co_destroy

Function Documentation

enhanced_suffix_array()

template<std::ranges::input_range R, class Compare = std::less<>>

step20::enhanced_suffix_array	(	R	,
		Compare	= {}
	)		-> enhanced_suffix_array< std::ranges::range_value_t< R >, std::size_t, Compare >

longest_repeated_substring() [1/2]

template<class... Ts>

auto step20::longest_repeated_substring

(

const enhanced_suffix_array< Ts... > &

arr

)

-> std::basic_string_view<typename enhanced_suffix_array<Ts...>::value_type>

Find the longest substring that occurs at least twice.

Substring is contiguous, while subsequence need not be. Time complexity O(N), where: N - text length.

longest_repeated_substring() [2/2]

template<class... Ts>

auto step20::longest_repeated_substring

(

const suffix_tree< Ts... > &

tree

)

-> std::basic_string_view<typename suffix_tree<Ts...>::value_type>

Find the longest substring that occurs at least twice.

Tree must be explicit - padded with a terminal symbol. Time complexity O(N), space complexity asymptotically close to O(log(N)), O(N) at worst, where: N - text length.

suffix_array()

template<std::ranges::input_range R, class Compare = std::less<>>

step20::suffix_array	(	R	,
		Compare	= {}
	)		-> suffix_array< std::ranges::range_value_t< R >, std::size_t, Compare >

to() [1/2]

template<class To , std::ranges::input_range From>

To step20::to

(

From &&

from

)

See also

https://en.cppreference.com/w/cpp/ranges/to

to() [2/2]

template<template< class... > class To, std::ranges::input_range From>

auto step20::to

(

From &&

from

)

Variable Documentation

co_destroy

auto step20::co_destroy

inline

Initial value:

= [](void* address) {
    std::coroutine_handle<>::from_address(address).destroy();
}