step20::edit_distance Namespace Reference

Functions
template<std::ranges::random_access_range R1, std::ranges::random_access_range R2, std::weakly_incrementable O, class Equal = std::equal_to<>>
O	zip (const R1 &r1, const R2 &r2, O result, const Equal &eq={})
	Find the optimal sequence alignment between two strings.

Function Documentation

zip()

template<std::ranges::random_access_range R1, std::ranges::random_access_range R2, std::weakly_incrementable O, class Equal = std::equal_to<>>

O step20::edit_distance::zip	(	const R1 &	r1,
		const R2 &	r2,
		O	result,
		const Equal &	eq = {}
	)

Find the optimal sequence alignment between two strings.

Optimality is measured with the Levenshtein distance, defined to be the sum of the costs of insertions, replacements, deletions, and null actions needed to change one string into the other. Time complexity O(N*M), space complexity O(min(N,M)), where: N = std::ranges::distance(r1), M = std::ranges::distance(r2).