String_DP.H File Reference

Dynamic-programming algorithms for string similarity and alignment. More...

#include <algorithm>
#include <string>
#include <string_view>
#include <array>
#include <tpl_array.H>

Include dependency graph for String_DP.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	Aleph::LCS_Result
	Result for Longest Common Subsequence (LCS). More...
struct	Aleph::Longest_Common_Substring_Result
	Result for longest common substring. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.
namespace	Aleph::string_dp_detail

Functions
Array< size_t >	Aleph::string_dp_detail::make_zero_row (const size_t cols)
Array< Array< size_t > >	Aleph::string_dp_detail::make_zero_matrix (const size_t rows, const size_t cols)
size_t	Aleph::levenshtein_distance (const std::string_view a, const std::string_view b)
	Levenshtein distance (insert/delete/substitute each cost 1).
size_t	Aleph::edit_distance (const std::string_view a, const std::string_view b)
	Alias for Levenshtein distance.
size_t	Aleph::damerau_levenshtein_distance (const std::string_view a, const std::string_view b)
	Damerau-Levenshtein distance with adjacent transpositions.
LCS_Result	Aleph::longest_common_subsequence (const std::string_view a, const std::string_view b)
	Compute Longest Common Subsequence.
Longest_Common_Substring_Result	Aleph::longest_common_substring (const std::string_view a, const std::string_view b)
	Compute the longest common substring (contiguous) between two strings.

Detailed Description

Dynamic-programming algorithms for string similarity and alignment.

Includes:

• Levenshtein edit distance
• Damerau-Levenshtein edit distance (full transposition model)
• LCS (Longest Common Subsequence)
• Longest Common Substring

Definition in file String_DP.H.