kz-maxx

RU KZ
← Басты бет

Ең ұзын ортақ подпоследовательность

LCS: екі строка бойынша динамикалық программалау

LCS деген не?

LCS — Longest Common Subsequence. Қазақша мағынасы: ең ұзын ортақ подпоследовательность.

Бізге екі строка беріледі. Сол екі строкада да кездесетін ең ұзын подпоследовательность табу керек.

Подпоследовательность дегеніміз — символдар міндетті түрде қатар тұрмайды. Символдарды өткізіп кетуге болады, бірақ порядок өзгермеуі керек.

Мысал

Екі строка берілсін: 

s = "abcde"
t = "ace"

Ортақ подпоследовательность: 

ace

Жауап: 

3

Себебі "ace" ұзындығы 3.

Подпоследовательность және подстрока

Термин Мағынасы Мысал
Подпоследовательность символдарды өткізіп кетуге болады "ace" из "abcde"
Подстрока символдар қатар тұруы керек "bcd" из "abcde"
LCS — подстрока емес, подпоследовательность.

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

Екі өлшемді DP қолданамыз: 

dp[i][j]

dp[i][j] — бірінші строканың алғашқы i символы және екінші строканың алғашқы j символы үшін LCS ұзындығы.

dp[i][j] = answer үшін s[0..i-1] және t[0..j-1]

Неге i және j керек?

Бізде екі строка бар. Сондықтан state екі параметрге байланысты:

  • i — бірінші строкадан қанша символ алдық
  • j — екінші строкадан қанша символ алдық
s = abcde
t = ace

dp[3][2] = answer үшін "abc" және "ac"

Базалық мәндер

Егер бір строка бос болса, ортақ подпоследовательность ұзындығы 0 болады. 

dp[0][j] = 0;
dp[i][0] = 0;

C++-та глобальный массив автоматты түрде 0 болып тұрады.

DP переход

Соңғы символдарды салыстырамыз: 

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

Егер олар тең болса, осы символды answer-ға қоса аламыз: 

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

Егер символдар әртүрлі болса, бір символды өткізіп көреміз: 

else {
    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}

Формула толық

if (s[i - 1] == t[j - 1]) {
    dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
символдар тең → осы символды аламыз
символдар әртүрлі → екі варианттың максимумын аламыз

Задача 1: LCS ұзындығын табу

Екі строка s және t берілген. Олардың ең ұзын ортақ подпоследовательность ұзындығын табу керек.

Input

abcde
ace

Output

3

LCS ұзындығын табу толық код

#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 = 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] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    cout << dp[n][m];

    return 0;
}

dp[n][m] қалай оқылады?

Егер: 

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

Онда: 

dp[n][m]

Бұл толық s және толық t строкалары үшін answer.

dp[n][m] = екі толық строканың LCS ұзындығы

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

Мысалы: 

s = "abc"
t = "ac"

Жауап: 

2

Себебі ортақ подпоследовательность — "ac".

State Мағынасы
dp[1][1] LCS("a", "a") = 1
dp[2][1] LCS("ab", "a") = 1
dp[3][2] LCS("abc", "ac") = 2

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

LCS-ті алдымен рекурсия арқылы түсінуге болады.

Функция: 

solve(i, j)

Бұл бірінші строканың алғашқы i символы және екінші строканың алғашқы j символы үшін LCS ұзындығы.

Егер i == 0 немесе j == 0, answer 0. 

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

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

Егер соңғы символдар тең болса: 

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

Егер соңғы символдар әртүрлі болса: 

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

Рекурсия + memoization

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

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

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

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

    if (s[i - 1] == t[j - 1]) {
        dp[i][j] = solve(i - 1, j - 1) + 1;
    } else {
        dp[i][j] = max(solve(i - 1, j), solve(i, 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]
solve(i - 1, j - 1) dp[i - 1][j - 1]
solve(i - 1, j) dp[i - 1][j]
solve(i, j - 1) dp[i][j - 1]
base case 0-жол және 0-баған

LCS-тің өзін қалпына келтіру

Кейде тек ұзындығын емес, нақты ортақ подпоследовательностьты шығару керек.

dp толық толтырылғаннан кейін артқа қарай жүреміз: 

i = n;
j = m;

Егер символдар тең болса, бұл символ answer ішінде бар: 

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

Егер символдар әртүрлі болса

Егер символдар әртүрлі болса, dp мәні үлкен жаққа барамыз. 

if (dp[i - 1][j] > dp[i][j - 1]) {
    i--;
} else {
    j--;
}

Жауап соңынан басына қарай жиналады. Сондықтан соңында: 

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

LCS қалпына келтіру коды

string answer;

int i = n;
int j = m;

while (i > 0 && j > 0) {
    if (s[i - 1] == t[j - 1]) {
        answer.push_back(s[i - 1]);
        i--;
        j--;
    } else if (dp[i - 1][j] > dp[i][j - 1]) {
        i--;
    } else {
        j--;
    }
}

reverse(answer.begin(), answer.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 = 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] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    string answer;

    int i = n;
    int j = m;

    while (i > 0 && j > 0) {
        if (s[i - 1] == t[j - 1]) {
            answer.push_back(s[i - 1]);
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }

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

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

    return 0;
}

Қалпына келтіру мысалы

Input

abac
cab

Output

2
ab

Басқа дұрыс answer болуы мүмкін, себебі LCS әрқашан жалғыз болмайды.

Memory optimization

Егер тек LCS ұзындығы керек болса, толық dp[n][m] сақтамай, тек екі строка сақтауға болады. 

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

Себебі dp[i][j] тек мына мәндерге байланысты:

  • dp[i - 1][j - 1]
  • dp[i - 1][j]
  • dp[i][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, 0);
    vector<int> cur(m + 1, 0);

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

        prev = cur;
    }

    cout << prev[m];

    return 0;
}
Егер нақты LCS-ті қалпына келтіру керек болса, толық dp[n][m] сақтау ыңғайлы.

LCS және LIS айырмашылығы

Задача Не беріледі? Не іздейміз?
LIS бір массив ең ұзын өсетін подпоследовательность
LCS екі строка немесе екі массив ең ұзын ортақ подпоследовательность

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

  • Подпоследовательность пен подстроканы шатастыру
  • Символдарды өткізіп кетуге болатынын ұмыту
  • s[i] орнына дұрыс s[i - 1] қолданбау
  • t[j] орнына дұрыс t[j - 1] қолданбау
  • 0-жол мен 0-бағанды дұрыс түсінбеу
  • Қалпына келтіруде reverse жасауды ұмыту
  • LCS әрқашан жалғыз деп ойлау

Асимптотика

Метод Уақыт Память
Рекурсия + memoization O(nm) O(nm)
Итеративный DP O(nm) O(nm)
Memory optimization O(nm) O(m)
Мұнда n — бірінші строка ұзындығы, m — екінші строка ұзындығы.

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

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

Қысқа шаблон

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

cout << dp[n][m];