Редакционное расстояние

@Abricos47 · Регистрация: 12.06.2020

Author24 — интернет-сервис помощи студентам

В информатике редакционным расстоянием между двумя строками называется минимальное количество добавлений, удалений и замен символов, при помощи которых можно из одной строки получить другую. К примеру, редакционное расстояние между строками “ab” и “ab” равно нулю, так как строки равны между собой безо всяких изменений; расстояние между строками “short” и “ports” равно трём: в слове “short” нужно удалить из начала букву ‘s’, заменить ‘h’ на ‘p’ и добавить в конец букву ‘s’. Редакционное расстояние также называют расстоянием Левенштейна.
Найдите редакционное расстояние между двумя заданными строками.

Формат ввода
В первой строчке входного файла задана одна строка, во второй — другая.
Длины строк от 1 до 100.

Формат вывода
В выходной файл выведите единственное число — редакционное расстояние между двумя заданными строками.

Ввод
ab
ab
Вывод
0

Ввод
short
ports

Вывод
3

@Super-Hacker · 14.06.2020, 21:16

https://habr.com/ru/post/117063/

Или же вы хотите реализацию

@nalbe666 · 14.06.2020, 21:29

C++

int LevenshteinDistance(const std::string& s1, const std::string& s2) {
    if (s1.empty()) return s2.size();
    if (s2.empty()) return s1.size();
 
    int* costs = new int[s2.size() + 1];
 
    for (int k = 0; k <= s2.size(); ++k) costs[k] = k;
 
    int i = 0;
    for (std::string::const_iterator it1 = s1.cbegin(); it1 != s1.cend(); ++it1, ++i) {
        costs[0] = i + 1;
        int corner = i;
        int j = 0;
        for (std::string::const_iterator it2 = s2.cbegin(); it2 != s2.cend(); ++it2, ++j) {
            int upper = costs[j + 1];
            if (*it1 == *it2) {
                costs[j + 1] = corner;
            }
            else {
                int t(upper < corner ? upper : corner);
                costs[j + 1] = (costs[j] < t ? costs[j] : t) + 1;
            }
            corner = upper;
        }
    }
    int result = costs[s2.size()];
 
    delete[] costs;
    return result;
}

@Abricos47 -8 / 0 / 0 Регистрация: 12.06.2020 Сообщений: 35
		1
	Редакционное расстояние 14.06.2020, 21:14. Показов 4780. Ответов 2 Метки спасибо (Все метки) В информатике редакционным расстоянием между двумя строками называется минимальное количество добавлений, удалений и замен символов, при помощи которых можно из одной строки получить другую. К примеру, редакционное расстояние между строками “ab” и “ab” равно нулю, так как строки равны между собой безо всяких изменений; расстояние между строками “short” и “ports” равно трём: в слове “short” нужно удалить из начала букву ‘s’, заменить ‘h’ на ‘p’ и добавить в конец букву ‘s’. Редакционное расстояние также называют расстоянием Левенштейна. Найдите редакционное расстояние между двумя заданными строками. Формат ввода В первой строчке входного файла задана одна строка, во второй — другая. Длины строк от 1 до 100. Формат вывода В выходной файл выведите единственное число — редакционное расстояние между двумя заданными строками. Ввод ab ab Вывод 0 Ввод short ports Вывод 3 0

@Super-Hacker 342 / 114 / 37 Регистрация: 26.11.2019 Сообщений: 735
	14.06.2020, 21:16	2
	https://habr.com/ru/post/117063/ Или же вы хотите реализацию 1

	14.06.2020, 21:29