step20::substring_search Namespace Reference

Functions
template<class... Ts>
auto	find_any (const suffix_array< Ts... > &arr, std::ranges::forward_range auto &&str) -> std::optional< typename suffix_array< Ts... >::size_type >
	Find substring offset.
template<class... Ts>
auto	find_all (const suffix_array< Ts... > &arr, std::basic_string< typename suffix_array< Ts... >::value_type > str) -> generator< typename suffix_array< Ts... >::size_type >
	Find all occurrences of the substring.
template<class... Ts>
auto	find_first (const suffix_tree< Ts... > &tree, std::ranges::forward_range auto &&str) -> std::optional< typename suffix_tree< Ts... >::size_type >
	Find offset of the first occurrence of the substring.
template<class... Ts>
auto	find_all (const suffix_tree< Ts... > &tree, std::basic_string< typename suffix_tree< Ts... >::value_type > str) -> generator< typename suffix_tree< Ts... >::size_type >
	Find all occurrences of substring.

Function Documentation

find_all() [1/2]

template<class... Ts>

auto step20::substring_search::find_all	(	const suffix_array< Ts... > &	arr,
		std::basic_string< typename suffix_array< Ts... >::value_type >	str
	)		-> generator<typename suffix_array<Ts...>::size_type>

Find all occurrences of the substring.

find_all() [2/2]

template<class... Ts>

auto step20::substring_search::find_all	(	const suffix_tree< Ts... > &	tree,
		std::basic_string< typename suffix_tree< Ts... >::value_type >	str
	)		-> generator<typename suffix_tree<Ts...>::size_type>

Find all occurrences of substring.

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

find_any()

template<class... Ts>

auto step20::substring_search::find_any	(	const suffix_array< Ts... > &	arr,
		std::ranges::forward_range auto &&	str
	)		-> std::optional<typename suffix_array<Ts...>::size_type>

Find substring offset.

Time complexity O(M*log(N)), where: M - substring length, N - text length.

find_first()

template<class... Ts>

auto step20::substring_search::find_first	(	const suffix_tree< Ts... > &	tree,
		std::ranges::forward_range auto &&	str
	)		-> std::optional<typename suffix_tree<Ts...>::size_type>

Find offset of the first occurrence of the substring.

Time complexity O(M), where: M - substring length.