Реализации алгоритмов/Расстояние Левенштейна: различия между версиями
Содержимое удалено Содержимое добавлено
Ilis (обсуждение | вклад) м →Python: PEP8 |
Отмена правки 152395, сделанной 37.1.141.176 (обсуждение). Был полностью нарушен coding style. Абсолютно не ясно почему возвращаемое значение имеет тип T::value_type, который для строки является char. Метка: отмена |
||
Строка 537:
template<typename T>
typename T::
const T &target) {
{▼
if (source.size() > target.size()) {
const typename T::size_type m = src.size;▼
return LevensteinDistance(target, source);
}▼
const TSizeType min_size = source.size(), max_size = target.size();
std::vector<TSizeType> lev_dist(min_size + 1);
for (TSizeType i = 0; i <= min_size; ++i) {
lev_dist[i] = i;
for (TSizeType j = 1; j <= max_size; ++j) {
TSizeType previous_diagonal = lev_dist[0], previous_diagonal_save;
++lev_dist[0];
for (TSizeType i = 1; i <= min_size; ++i) {
previous_diagonal_save = lev_dist[i];
if (source[i - 1] == target[j - 1]) {
lev_dist[i] = previous_diagonal;
} else {
lev_dist[i] = std::min(std::min(lev_dist[i - 1], lev_dist[i]), previous_diagonal) + 1;
}
previous_diagonal = previous_diagonal_save;
}
}
return lev_dist[min_size];
▲}
</source>
Пример использования:
<source lang="CPP">
|