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

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

Обычно разрешены три операции:

• insert — вставить символ
• delete — удалить символ
• replace — заменить один символ на другой

Пример

Нужно превратить строку:

cat

в строку:

cut

Достаточно заменить a на u.

Еще пример

Нужно превратить:

kitten

в:

sitting

Один из вариантов:

Всего 3 операции.

answer = 3

Где используется?

• исправление ошибок в словах
• поиск похожих строк
• автозамена
• сравнение текстов
• биоинформатика
• алгоритмы поиска
• задачи на DP по строкам

Главная идея DP

У нас есть две строки:

string s, t;

Придумаем состояние:

dp[i][j]

dp[i][j] — минимальное количество операций, чтобы превратить первые i символов строки s в первые j символов строки t.

Почему два индекса?

Потому что мы сравниваем две строки.

• i — сколько символов взяли из первой строки
• j — сколько символов взяли из второй строки

s = horse
t = ros

dp[3][2] = расстояние между "hor" и "ro"

Базовые значения

Если первая строка пустая, а во второй строке j символов, нужно вставить все j символов.

dp[0][j] = j;

Если вторая строка пустая, а в первой строке i символов, нужно удалить все i символов.

dp[i][0] = i;

Переход DP

Смотрим последние символы текущих префиксов:

s[i - 1]
t[j - 1]

Если они равны, ничего делать не надо:

dp[i][j] = dp[i - 1][j - 1];

Если они разные, выбираем минимум из трех операций:

• удалить символ
• вставить символ
• заменить символ

Три операции

Удаление символа из первой строки:

dp[i - 1][j] + 1

Вставка символа в первую строку:

dp[i][j - 1] + 1

Замена символа:

dp[i - 1][j - 1] + 1

Формула целиком

if (s[i - 1] == t[j - 1]) {
    dp[i][j] = dp[i - 1][j - 1];
} else {
    dp[i][j] = min({
        dp[i - 1][j] + 1,
        dp[i][j - 1] + 1,
        dp[i - 1][j - 1] + 1
    });
}

Задача 1: найти редакционное расстояние

Даны две строки s и t. Нужно найти минимальное количество операций, чтобы превратить s в t.

Input

horse
ros

Output

3

Полная реализация

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

const int N = 1010;

string s, t;
int dp[N][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> s >> t;

    int n = s.size();
    int m = t.size();

    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++) {
            if (s[i - 1] == t[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = min({
                    dp[i - 1][j] + 1,
                    dp[i][j - 1] + 1,
                    dp[i - 1][j - 1] + 1
                });
            }
        }
    }

    cout << dp[n][m];

    return 0;
}

Как читать dp[n][m]?

Если:

n = s.size();
m = t.size();

Тогда:

dp[n][m]

Это расстояние между всей строкой s и всей строкой t.

Пример руками

Пусть:

s = "cat"
t = "cut"

Символы:

Всего нужна 1 операция.

answer = 1

Рекурсивный метод

Сначала можно думать рекурсивно.

Пусть:

solve(i, j)

Это минимальное количество операций, чтобы превратить первые i символов s в первые j символов t.

Рекурсивные базовые случаи

Если i == 0, значит первая строка пустая. Нужно вставить j символов.

if (i == 0) {
    return j;
}

Если j == 0, значит вторая строка пустая. Нужно удалить i символов.

if (j == 0) {
    return i;
}

Рекурсивный переход

Если последние символы равны:

solve(i, j) = solve(i - 1, j - 1)

Если разные:

solve(i, j) = 1 + min(
    solve(i - 1, j),
    solve(i, j - 1),
    solve(i - 1, j - 1)
)

Рекурсия + мемоизация

int solve(int i, int j) {
    if (i == 0) {
        return j;
    }

    if (j == 0) {
        return i;
    }

    if (dp[i][j] != -1) {
        return dp[i][j];
    }

    if (s[i - 1] == t[j - 1]) {
        dp[i][j] = solve(i - 1, j - 1);
    } else {
        dp[i][j] = 1 + min({
            solve(i - 1, j),
            solve(i, j - 1),
            solve(i - 1, j - 1)
        });
    }

    return dp[i][j];
}

Полная рекурсивная реализация

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

const int N = 1010;

string s, t;
int dp[N][N];

int solve(int i, int j) {
    if (i == 0) {
        return j;
    }

    if (j == 0) {
        return i;
    }

    if (dp[i][j] != -1) {
        return dp[i][j];
    }

    if (s[i - 1] == t[j - 1]) {
        dp[i][j] = solve(i - 1, j - 1);
    } else {
        dp[i][j] = 1 + min({
            solve(i - 1, j),
            solve(i, j - 1),
            solve(i - 1, j - 1)
        });
    }

    return dp[i][j];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> s >> t;

    memset(dp, -1, sizeof(dp));

    cout << solve(s.size(), t.size());

    return 0;
}

Рекурсия → итеративный DP

Восстановление операций

Иногда нужно вывести не только число операций, но и сами операции.

После заполнения dp идем назад из:

i = n;
j = m;

Если символы равны, просто идем назад:

if (s[i - 1] == t[j - 1]) {
    i--;
    j--;
}

Как понять операцию?

Если текущее значение пришло из dp[i - 1][j] + 1, значит был delete.

if (dp[i][j] == dp[i - 1][j] + 1) {
    // delete s[i - 1]
}

Если пришло из dp[i][j - 1] + 1, значит был insert.

if (dp[i][j] == dp[i][j - 1] + 1) {
    // insert t[j - 1]
}

Если пришло из dp[i - 1][j - 1] + 1, значит был replace.

Код восстановления операций

vector<string> ops;

int i = n;
int j = m;

while (i > 0 || j > 0) {
    if (i > 0 && j > 0 && s[i - 1] == t[j - 1]) {
        i--;
        j--;
    } else if (i > 0 && dp[i][j] == dp[i - 1][j] + 1) {
        ops.push_back("delete");
        i--;
    } else if (j > 0 && dp[i][j] == dp[i][j - 1] + 1) {
        ops.push_back("insert");
        j--;
    } else {
        ops.push_back("replace");
        i--;
        j--;
    }
}

reverse(ops.begin(), ops.end());

Полная реализация с операциями

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

const int N = 1010;

string s, t;
int dp[N][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> s >> t;

    int n = s.size();
    int m = t.size();

    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++) {
            if (s[i - 1] == t[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = min({
                    dp[i - 1][j] + 1,
                    dp[i][j - 1] + 1,
                    dp[i - 1][j - 1] + 1
                });
            }
        }
    }

    cout << dp[n][m] << '\n';

    vector<string> ops;

    int i = n;
    int j = m;

    while (i > 0 || j > 0) {
        if (i > 0 && j > 0 && s[i - 1] == t[j - 1]) {
            i--;
            j--;
        } else if (i > 0 && dp[i][j] == dp[i - 1][j] + 1) {
            ops.push_back("delete " + string(1, s[i - 1]));
            i--;
        } else if (j > 0 && dp[i][j] == dp[i][j - 1] + 1) {
            ops.push_back("insert " + string(1, t[j - 1]));
            j--;
        } else {
            ops.push_back("replace " + string(1, s[i - 1]) + " to " + string(1, t[j - 1]));
            i--;
            j--;
        }
    }

    reverse(ops.begin(), ops.end());

    for (string op : ops) {
        cout << op << '\n';
    }

    return 0;
}

Оптимизация памяти

Если нужно только расстояние, можно хранить не всю таблицу, а только две строки:

vector<int> prev(m + 1);
vector<int> cur(m + 1);

Потому что dp[i][j] зависит только от:

• dp[i - 1][j]
• dp[i][j - 1]
• dp[i - 1][j - 1]

Реализация с памятью O(m)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s, t;
    cin >> s >> t;

    int n = s.size();
    int m = t.size();

    vector<int> prev(m + 1);
    vector<int> cur(m + 1);

    for (int j = 0; j <= m; j++) {
        prev[j] = j;
    }

    for (int i = 1; i <= n; i++) {
        cur[0] = i;

        for (int j = 1; j <= m; j++) {
            if (s[i - 1] == t[j - 1]) {
                cur[j] = prev[j - 1];
            } else {
                cur[j] = min({
                    prev[j] + 1,
                    cur[j - 1] + 1,
                    prev[j - 1] + 1
                });
            }
        }

        prev = cur;
    }

    cout << prev[m];

    return 0;
}

Связь с LCS

Редакционное расстояние похоже на LCS, потому что обе задачи работают с двумя строками и используют состояние dp[i][j].

Типичные ошибки

• Забыть инициализировать dp[0][j]
• Забыть инициализировать dp[i][0]
• Писать s[i] вместо s[i - 1]
• Писать t[j] вместо t[j - 1]
• Забыть +1 при операции
• Путать insert и delete при восстановлении
• Думать, что если символы равны, надо все равно делать +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++) {
        if (s[i - 1] == t[j - 1]) {
            dp[i][j] = dp[i - 1][j - 1];
        } else {
            dp[i][j] = min({
                dp[i - 1][j] + 1,
                dp[i][j - 1] + 1,
                dp[i - 1][j - 1] + 1
            });
        }
    }
}

cout << dp[n][m];