step20::longest_common_substring Namespace Reference

Functions
template<std::ranges::input_range R1, std::ranges::input_range R2, std::weakly_incrementable O, class Compare = std::less<>>
O	copy (const R1 &r1, const R2 &r2, O result, const Compare &comp={})
	Find the longest substring of two strings.

Function Documentation

copy()

template<std::ranges::input_range R1, std::ranges::input_range R2, std::weakly_incrementable O, class Compare = std::less<>>

O step20::longest_common_substring::copy	(	const R1 &	r1,
		const R2 &	r2,
		O	result,
		const Compare &	comp = {}
	)

Find the longest substring of two strings.

Substring is contiguous, while subsequence need not be. Time complexity O((N+M)*log(N+M)*log(N+M)), space complexity O(N+M), where: N = std::ranges::distance(r1), M = std::ranges::distance(r2).

See also

enhanced_suffix_array is used under the hood.