7.5 Расстояние редактирования¶

Расстояние редактирования (или расстояние Левенштейна) — это минимальное число операций, необходимых, чтобы превратить одну строку в другую.

Разрешённые операции:

• вставить символ;
• удалить символ;
• заменить один символ на другой.

Например, рассмотрим строки КОТ и СКАТ. Их расстояние редактирования равно 2:

• КОТ → СКОТ — вставили символ С;
• СКОТ → СКАТ — заменили О на А.

Меньше чем за две операции получить нужную строку нельзя.

Идея динамического программирования¶

Пусть дана строка x длины n и строка y длины m.

Будем считать, что dp[a][b] — это минимальное число операций, чтобы превратить префикс x[0..a-1] в префикс y[0..b-1].

Тогда ответом будет значение dp[n][m].

Базовые случаи¶

• dp[0][b] = b, потому что пустую строку можно превратить в первые b символов строки y, только вставляя символы;
• dp[a][0] = a, потому что строку длины a можно превратить в пустую, только удаляя символы.

Переход¶

Если мы хотим вычислить dp[a][b], есть три естественных варианта:

1. Вставить последний символ строки y:

$$ dp[a][b-1] + 1 $$

1. Удалить последний символ строки x:

$$ dp[a-1][b] + 1 $$

1. Сопоставить или заменить последний символ:

$$ dp[a-1][b-1] + cost(a,b) $$

где

Итак, получаем формулу:

Как это интерпретировать¶

Каждый переход отвечает за одно из возможных последних действий:

• dp[a][b-1] + 1 — в конец текущей строки добавили символ;
• dp[a-1][b] + 1 — удалили последний символ;
• dp[a-1][b-1] + cost(a,b) — если символы совпадают, просто оставили их как есть, иначе заменили один на другой.

Пример¶

Возьмём строки:

• x = "КОТ"
• y = "СКАТ"

Построим таблицу dp. Строки соответствуют префиксам x, столбцы — префиксам y.

В правом нижнем углу стоит число 2, значит расстояние редактирования равно 2.

Восстановление ответа¶

По таблице можно не только узнать число операций, но и восстановить один из оптимальных способов преобразования.

Для нашего примера путь может быть таким:

• КОТ
• СКОТ — вставили С в начало;
• СКАТ — заменили О на А.

Схема переходов¶

flowchart TD
    A["dp[a][b]"] --> B["dp[a][b-1] + 1 \n вставка"]
    A --> C["dp[a-1][b] + 1 \n удаление"]
    A --> D["dp[a-1][b-1] + cost \n совпадение или замена"]

Реализация на C++¶

#include <bits/stdc++.h>
using namespace std;

int main() {
    string x, y;
    cin >> x >> y;

    int n = (int)x.size();
    int m = (int)y.size();

    vector<vector<int>> dp(n + 1, vector<int>(m + 1));

    for (int i = 0; i <= n; i++) dp[i][0] = i;
    for (int j = 0; j <= m; j++) dp[0][j] = j;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int cost = (x[i - 1] == y[j - 1] ? 0 : 1);
            dp[i][j] = min({
                dp[i][j - 1] + 1,
                dp[i - 1][j] + 1,
                dp[i - 1][j - 1] + cost
            });
        }
    }

    cout << dp[n][m] << "\n";
    return 0;
}

Сложность¶

Таблица имеет размер (n+1) × (m+1), и каждую клетку мы вычисляем за O(1).

Итого:

• время: O(nm);
• память: O(nm).

Если нужен только ответ, а не восстановление пути, память можно уменьшить до O(m), храня только две соседние строки таблицы.

Что важно запомнить¶

Расстояние редактирования — классический пример динамического программирования по двум строкам.

Ключевая идея здесь такая:

• рассматриваем префиксы строк;
• понимаем, чем мог закончиться оптимальный ответ;
• выбираем минимум из трёх переходов: вставка, удаление, замена.

Этот приём встречается очень часто и полезен не только для расстояния Левенштейна, но и для многих задач на сравнение строк.