Реализации алгоритмов/Расстояние Левенштейна: различия между версиями
Содержимое удалено Содержимое добавлено
Строка 541:
template<typename T>
typename T::
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,n+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 j=0; j<=n; ++j){
matrix[0][j] =j;}
typename T::valuetype above_cell, left_cell, diagonal_cell, cost);
for (typename T::size_type i=1; i<=m; ++i){
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);
}
}
return matrix[m][n];
▲ using TSizeType = typename T::size_type;
}▼
▲}
Пример использования:
<source lang="CPP">
|