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

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

Редакционное расстояние — бір строканы екінші строкаға айналдыру үшін керек минималды операция саны.

Көбіне 3 операция рұқсат:

insert — символ қосу
delete — символ өшіру
replace — бір символды басқа символға ауыстыру

Бұл алгоритм Levenshtein Distance деп те аталады.

Қарапайым мысал

Мына строканы:

cat

мына строкаға айналдыру керек:

cut

Тек a символын u символына ауыстырамыз.

cat → cut
replace a to u
answer = 1

Тағы бір мысал

Мына строканы:

kitten

мына строкаға айналдыру керек:

sitting

Бір вариант:

kitten → sitten
sitten → sittin
sittin → sitting

Барлығы 3 операция.

answer = 3

Қай жерде қолданылады?

сөздегі қателерді түзету
ұқсас строкаларды табу
автозамена
мәтіндерді салыстыру
биоинформатика
search алгоритмдері
DP по строкам задачалары

DP негізгі идеясы

Бізде екі строка бар:

string s, t;

State ойлаймыз:

dp[i][j]

dp[i][j] — бірінші строканың алғашқы i символын екінші строканың алғашқы j символына айналдыру үшін керек минималды операция саны.

dp[i][j] = distance between s[0..i-1] and t[0..j-1]

Неге екі индекс керек?

Себебі біз екі строканы салыстырамыз.

i — бірінші строкадан қанша символ алдық
j — екінші строкадан қанша символ алдық

s = horse
t = ros

dp[3][2] = distance between "hor" and "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];

Егер әртүрлі болса, 3 операцияның минимумын аламыз:

delete
insert
replace

Үш операция

Delete — бірінші строкадан символ өшіру:

dp[i - 1][j] + 1

Insert — бірінші строкаға символ қосу:

dp[i][j - 1] + 1

Replace — символды ауыстыру:

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
    });
}

символдар тең → операция керек емес
символдар әртүрлі → delete, insert, replace ішінен minimum

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

Екі строка s және t берілген. s-ті t-ға айналдыру үшін минималды операция санын табу керек.

Input

horse
ros

Output

Толық реализация

#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 строкасына айналдыру үшін керек минималды операция саны.

dp[n][m] = minimum operations
to transform s into t

Қолмен түсіну мысалы

Мысалы:

s = "cat"
t = "cut"

Позиция	s	t	Не істейміз?
1	c	c	бірдей
2	a	u	replace
3	t	t	бірдей

Барлығы 1 операция керек.

answer = 1

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

Бұл задачаны алдымен рекурсия арқылы түсінуге болады.

Функция:

solve(i, j)

Бұл алғашқы i символды s-тен алып, алғашқы j символды t-ға айналдыру үшін керек minimum operation саны.

Рекурсивный базалық жағдайлар

Егер 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)
)

Рекурсия + memoization

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
solve(i, j)	dp[i][j]
if (i == 0) return j	dp[0][j] = j
if (j == 0) return i	dp[i][0] = i
solve(i - 1, j)	dp[i - 1][j]
solve(i, j - 1)	dp[i][j - 1]
solve(i - 1, j - 1)	dp[i - 1][j - 1]

Операцияларды қалпына келтіру

Кейде тек операция санын емес, нақты қандай операциялар жасалғанын шығару керек.

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;
}

Memory optimization

Егер тек distance керек болса, толық таблица сақтамай, тек екі строка сақтауға болады:

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;
}

Егер операцияларды қалпына келтіру керек болса, толық dp[n][m] сақтау ыңғайлы.

LCS-пен байланысы

Редакционное расстояние LCS-ке ұқсайды. Екеуі де екі строкамен жұмыс істейді және dp[i][j] state қолданады.

Задача	Не іздейміз?	State
LCS	ең ұзын ортақ подпоследовательность	dp[i][j]
Edit Distance	минималды операция саны	dp[i][j]

Типтік қателер

dp[0][j] инициализациясын ұмыту
dp[i][0] инициализациясын ұмыту
s[i] орнына дұрыс s[i - 1] қолданбау
t[j] орнына дұрыс t[j - 1] қолданбау
Операция кезінде +1 қосуды ұмыту
Қалпына келтіруде insert пен delete шатастыру
Символдар тең болса да +1 қосу

Асимптотика

Метод	Уақыт	Память
Рекурсия + memoization	O(nm)	O(nm)
Итеративный DP	O(nm)	O(nm)
Memory optimization	O(nm)	O(m)

Мұнда n — бірінші строка ұзындығы, m — екінші строка ұзындығы.

Задачада қалай ойлау керек?

1. Екі строка бар
2. Бір строканы екіншісіне айналдыру керек
3. State: dp[i][j]
4. Символдар тең болса — ештеңе істемейміз
5. Символдар әртүрлі болса — delete, insert, replace
6. Answer dp[n][m] ішінде

Қысқа шаблон

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];