Реализации алгоритмов/Расстояние Левенштейна: различия между версиями

Содержимое удалено Содержимое добавлено
→‎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 &ssource,
const T &ttarget) {
if (ssource.size() > ttarget.size()) {
return LevensteinDistance(ttarget, ssource);
}
 
using T_size_t = typename T::size_type;
const T_size_t min_size = ssource.size(), max_size = ttarget.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 (ssource[i - 1] == ttarget[j - 1]) {
lev_dist[i] = previous_diagonal;
} else {
Строка 594 ⟶ 597 :
 
template<typename T>
typename T::size_type GeneralizedLevensteinDistance(const T &ssource,
const T &ttarget,
typename T::size_type insert_cost = 1,
typename T::size_type delete_cost = 1,
typename T::size_type replace_cost = 1) {
if (ssource.size() > ttarget.size()) {
return GeneralizedLevensteinDistance(ttarget, ssource, delete_cost, insert_cost, replace_cost);
}
 
using T_size_t = typename T::size_type;
const T_size_t min_size = ssource.size(), max_size = ttarget.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 (ssource[i - 1] == ttarget[j - 1]) {
lev_dist[i] = previous_diagonal;
} else {