Викиучебник

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

Интерактивная навигация по истории
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
→‎C++: Изменёны названия переменных s -> source, t -> target
→‎C++: Имя типа изменено под Google C++ Style Guide
Строка 547:
}
 
using T_size_tTSizeType = typename T::size_type;
const T_size_tTSizeType min_size = source.size(), max_size = target.size();
std::vector<T_size_tTSizeType> lev_dist(min_size + 1);
 
for (T_size_tTSizeType i = 0; i <= min_size; ++i) {
lev_dist[i] = i;
}
 
for (T_size_tTSizeType j = 1; j <= max_size; ++j) {
T_size_tTSizeType previous_diagonal = lev_dist[0], previous_diagonal_save;
++lev_dist[0];
 
for (T_size_tTSizeType i = 1; i <= min_size; ++i) {
previous_diagonal_save = lev_dist[i];
if (source[i - 1] == target[j - 1]) {
Строка 606:
}
 
using T_size_tTSizeType = typename T::size_type;
const T_size_tTSizeType min_size = source.size(), max_size = target.size();
std::vector<T_size_tTSizeType> lev_dist(min_size + 1);
 
lev_dist[0] = 0;
for (T_size_tTSizeType i = 1; i <= min_size; ++i) {
lev_dist[i] = lev_dist[i - 1] + delete_cost;
}
 
for (T_size_tTSizeType j = 1; j <= max_size; ++j) {
T_size_tTSizeType previous_diagonal = lev_dist[0], previous_diagonal_save;
lev_dist[0] += insert_cost;
 
for (T_size_tTSizeType i = 1; i <= min_size; ++i) {
previous_diagonal_save = lev_dist[i];
if (source[i - 1] == target[j - 1]) {
Источник — https://ru.wikibooks.org/wiki/Реализации_алгоритмов/Расстояние_Левенштейна