2.4.2.5 — та же таблица, что у LCS, но другая логика перехода2.4.2.5 — the same table as LCS, but different transition logic
Расстояние Левенштейна между двумя строками — минимальное число операций вставки, удаления или замены символа, чтобы превратить одну строку в другую. Это прямое обобщение наибольшей общей подпоследовательности (2.4.2.2): та же самая 2D-таблица "первые i символов A, первые j символов B", но переход считает не длину совпадения, а стоимость расхождения. Понимание LCS почти напрямую переносится сюда — если освоена одна статья, вторая требует только заменить одну формулу перехода, а не учить структуру заново.The Levenshtein distance between two strings is the minimum number of insert, delete, or replace operations needed to turn one string into the other. This is a direct generalization of the longest common subsequence (2.4.2.2): the exact same 2D table "first i characters of A, first j characters of B," but the transition tracks the cost of divergence instead of the length of agreement. Understanding LCS carries over almost directly — once one article is mastered, the other only requires swapping one transition formula, not relearning the structure.
Пусть dp[i][j] — минимальное число операций, чтобы превратить первые i символов строки A в первые j символов строки B. Если последние символы совпадают (A[i-1] == B[j-1]), никакая операция не нужна на этом шаге — задача сводится к превращению более коротких префиксов: dp[i][j] = dp[i-1][j-1]. Если символы не совпадают, нужна ровно одна операция плюс решение одной из трёх более простых подзадач: удалить последний символ A (dp[i-1][j] + 1 — теперь нужно превратить укороченный префикс A в весь префикс B), вставить символ B в конец A (dp[i][j-1] + 1 — префикс A остаётся как есть, но нужно ещё "вписать" последний символ B), или заменить последний символ A на нужный (dp[i-1][j-1] + 1 — оба префикса укорачиваются, но добавляется одна операция замены). Берём минимум из трёх: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]). Базовый случай: dp[i][0] = i (удалить все i символов A), dp[0][j] = j (вставить все j символов B).Let dp[i][j] be the minimum number of operations to turn the first i characters of A into the first j characters of B. If the last characters match (A[i-1] == B[j-1]), no operation is needed at this step — the problem reduces to transforming the shorter prefixes: dp[i][j] = dp[i-1][j-1]. If they don't match, exactly one operation is needed plus the solution to one of three simpler subproblems: delete A's last character (dp[i-1][j] + 1 — now the shortened A-prefix must become the entire B-prefix), insert B's character at the end of A (dp[i][j-1] + 1 — A's prefix stays as-is, but B's last character still needs to be "written in"), or replace A's last character with the needed one (dp[i-1][j-1] + 1 — both prefixes shrink, but one replace operation is added). Take the minimum of the three: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]). The base case: dp[i][0] = i (delete all i characters of A), dp[0][j] = j (insert all j characters of B).
Сравнение с LCS (2.4.2.2) показывает, насколько похожи обе задачи структурно: там при совпадении символов идут по диагонали с ПРИБАВЛЕНИЕМ единицы (расширяем общую подпоследовательность), здесь при совпадении идут по диагонали БЕЗ добавления (совпадение — это "бесплатная" операция, которую не нужно оплачивать). Там при несовпадении берут максимум из верхней и левой ячейки, здесь при несовпадении берут минимум из трёх ячеек (верх, лево, диагональ) плюс единица за саму операцию. Это не совпадение — обе задачи выражают одну и ту же идею "сравнить два префикса и решить их подзадачи", просто с разными критериями оптимизации (максимизировать совпадения против минимизировать операции).Comparing with LCS (2.4.2.2) shows just how structurally similar the two problems are: there, on a match, the diagonal move ADDS one (extending the common subsequence); here, on a match, the diagonal move adds NOTHING (a match is a "free" operation that costs nothing). There, on a mismatch, the max of the cell above and to the left is taken; here, on a mismatch, the minimum of three cells (above, left, diagonal) plus one is taken for the operation itself. This isn't a coincidence — both problems express the same idea of "compare two prefixes and solve their subproblems," just with different optimization criteria (maximize matches versus minimize operations).
Восстановление последовательности операций — обратный проход от dp[n][m]: если A[i-1] == B[j-1] и dp[i][j] == dp[i-1][j-1], символ совпал (без операции) — переходим по диагонали; иначе смотрим, откуда пришёл минимум — из dp[i-1][j-1] (замена), dp[i-1][j] (удаление) или dp[i][j-1] (вставка), — записываем соответствующую операцию и переходим в найденную ячейку.Reconstructing the operation sequence is a backward pass from dp[n][m]: if A[i-1] == B[j-1] and dp[i][j] == dp[i-1][j-1], the character matched (no operation) — move diagonally; otherwise check which cell the minimum came from — dp[i-1][j-1] (replace), dp[i-1][j] (delete), or dp[i][j-1] (insert) — record the corresponding operation and move to that cell.
три источника вместо двух у LCS — диагональ добавлена как явный вариант "замена"three sources instead of LCS's two — the diagonal is added as an explicit "replace" option
int editDistance(const std::string& a, const std::string& b) {
int n = a.size(), m = b.size();
std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1));
for (int i = 0; i <= n; i++) dp[i][0] = i; // удалить всё A// delete all of A
for (int j = 0; j <= m; j++) dp[0][j] = j; // вставить всё B// insert all of B
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (a[i-1] == b[j-1])
dp[i][j] = dp[i-1][j-1]; // совпадение — бесплатно// a match — free
else
dp[i][j] = 1 + std::min({dp[i-1][j], // удаление// delete
dp[i][j-1], // вставка// insert
dp[i-1][j-1]}); // замена// replace
return dp[n][m];
}Две короткие строки — демонстрация проигрывает заполнение таблицы ячейка за ячейкой, а затем восстанавливает конкретную последовательность операций (удаление/вставка/замена/совпадение) обратным проходом от правого нижнего угла.Two short strings — the demo auto-plays filling the table cell by cell, then reconstructs the actual sequence of operations (delete/insert/replace/match) with a backward pass from the bottom-right corner.
введите две строки (до 7 символов каждая) и нажмите «запустить»enter two strings (up to 7 characters each) and press "run"
Проверка орфографии ранжирует кандидатов на исправление опечатки по редакционному расстоянию до введённого слова; системы автодополнения и поисковые системы используют ту же метрику (или ограниченные варианты вроде расстояния Дамерау—Левенштейна, добавляющего перестановку соседних символов) для нечёткого сопоставления запросов.Spell-checkers rank typo-correction candidates by edit distance to the typed word; autocomplete systems and search engines use the same metric (or bounded variants like Damerau–Levenshtein distance, which also allows transposing adjacent characters) for fuzzy query matching.
Алгоритм Нидлмана—Вунша для глобального выравнивания ДНК и белковых последовательностей — прямое обобщение редакционного расстояния, где стоимости вставки/удаления/замены заменены на биологически осмысленные веса (например, матрицы замен BLOSUM/PAM), а не фиксированную единицу за операцию.The Needleman–Wunsch algorithm for global alignment of DNA and protein sequences is a direct generalization of edit distance, where insert/delete/replace costs are replaced with biologically meaningful weights (e.g. BLOSUM/PAM substitution matrices) rather than a fixed cost of one per operation.