Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
fuzzy substring
// ==========================================================
template <typename T>
typename T::value_type levenshtein_distance(const T& src, const T& dst) {
const typename T::size_type m = src.size();
const typename T::size_type n = dst.size();
if (m == 0) {
return n;
}
if (n == 0) {
return m;
}
std::vector<std::vector<typename T::value_type>> matrix(m + 1);
for (typename T::size_type i = 0; i <= m; ++i) {
matrix[i].resize(n + 1);
matrix[i][0] = i;
}
for (typename T::size_type i = 0; i <= n; ++i) {
matrix[0][i] = 0;
}
typename T::value_type above_cell, left_cell, diagonal_cell, cost, min;
for (typename T::size_type i = 1; i <= m; ++i) {
min = std::numeric_limits<typename T::value_type>::max();
for(typename T::size_type j = 1; j <= n ; ++j) {
cost = src[i - 1] == dst[j - 1] ? 0 : 1;
above_cell = matrix[i - 1][j];
left_cell = matrix[i][j - 1];
diagonal_cell = matrix[i - 1][j - 1];
matrix[i][j] = std::min(std::min(above_cell + 1, left_cell + 1), diagonal_cell + cost);
min = std::min(min, matrix[i][j]);
}
}
/*
for (typename T::size_type i = 0; i < matrix.size(); ++i) {
for(typename T::size_type j = 0; j < matrix[i].size() ; ++j) {
printf("%d", matrix[i][j]);
}
printf("\n");
}
*/
return min;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment