Реализации алгоритмов/Расстояние Левенштейна: различия между версиями
Содержимое удалено Содержимое добавлено
→C++: Изменён код C++. Теперь он использует min(m, n) памяти вместо m * n памяти. Добавлено код на обобщённое расстояние Левенштейна |
→C++: Изменёны названия переменных s -> source, t -> target |
||
Строка 537:
-->
<source lang="CPP">
#include <algorithm>
#include <vector>
template<typename T>
typename T::size_type LevensteinDistance(const T &
const T &
if (
return LevensteinDistance(
}
using T_size_t = typename T::size_type;
const T_size_t min_size =
std::vector<T_size_t> lev_dist(min_size + 1);
Строка 558 ⟶ 561 :
for (T_size_t i = 1; i <= min_size; ++i) {
previous_diagonal_save = lev_dist[i];
if (
lev_dist[i] = previous_diagonal;
} else {
Строка 594 ⟶ 597 :
template<typename T>
typename T::size_type GeneralizedLevensteinDistance(const T &
const T &
typename T::size_type insert_cost = 1,
typename T::size_type delete_cost = 1,
typename T::size_type replace_cost = 1) {
if (
return GeneralizedLevensteinDistance(
}
using T_size_t = typename T::size_type;
const T_size_t min_size =
std::vector<T_size_t> lev_dist(min_size + 1);
Строка 618 ⟶ 621 :
for (T_size_t i = 1; i <= min_size; ++i) {
previous_diagonal_save = lev_dist[i];
if (
lev_dist[i] = previous_diagonal;
} else {
|