Хоёр string-д хоёуланд нь байгаа хамгийн урт нийтлэг дэд дарааллыг (LCS) хоёр хэмжээст хүснэгтээр олно.

Advanced & LegendХугацаа: O(n · m)Санах ой: O(n · m)
HackerRank дээр бодох

Эхлээд жижиг бодлого

s = "ABC", t = "ACB" хоёр string байна. Хоёуланд нь байгаа хамгийн урт дэд дараалал юу вэ? Үсэг алгасаж болно, харин дарааллыг нь сольж болохгүй.

"AB" нь s-д байна, t-д A-ийн дараа B бий. "AC" ч бас болно. "ABC" бол t-д C нь B-ээс өмнө байгаа тул болохгүй. Хариу 2.

Энгийн аргаас санаа руу

Энгийн арга бол s-ийн бүх дэд дарааллыг үүсгээд t-д байгаа эсэхийг шалгах. n үсэгтэй s-д 2ⁿ дэд дараалал бий.

Гол санаа: хоёр string-ийн сүүлийн үсгийг харна. Ижил бол тэр үсэг хариунд орно: dp[i][j] = dp[i - 1][j - 1] + 1. Өөр бол хоёулаа хариунд сүүлд нь орж чадахгүй, аль нэгийг нь хаяна: max(dp[i - 1][j], dp[i][j - 1]). Хүснэгтийг мөр мөрөөр бөглөнө.

Нэр томьёо ба тэмдэглэгээ

dp[i][j]
State: s-ийн эхний i үсэг ба t-ийн эхний j үсгийн хамгийн урт нийтлэг дэд дараалал.
s[i - 1]
s-ийн i дэх үсэг. String 0-ээс, хүснэгт 1-ээс эхэлдэг тул нэгийг хасна.
дэд дараалал
Үсэг алгасаж болно, дараалал нь хадгалагдана. Substring бол зэргэлдээ байх ёстой, энэ нь өөр.
LCS
Longest Common Subsequence, хамгийн урт нийтлэг дэд дараалал.
s \ tBDCAB​A​
0
0
0
0
0
0
0
A
0
B
0
C
0
B
0
D
0
A
0

ABCBDA ба BDCABA хоёр string-д хоёуланд нь байгаа хамгийн урт дэд дарааллыг олъё. Үсэг алгасаж болно, харин дарааллыг нь сольж болохгүй. State: dp[i][j] нь s-ийн эхний i үсэг, t-ийн эхний j үсгийн хариу.

Алхам 1 / 38
Хурд
  • Бөглөж буй нүд
  • Transition-д уншиж буй нүд
  • Бөглөсөн
  • 0: хоосон string
  • Нийтлэг үсгүүд
Слайд 1 / 6

Нийтлэг дэд дараалал

ABCBDA ба BDCABA хоёуланд нь байгаа хамгийн урт дэд дараалал юу вэ? Үсэг алгасаж болно, харин дарааллыг нь сольж болохгүй. Жишээ нь BDA хоёуланд нь бий.

lcs.cpp
#include <bits/stdc++.h>
using namespace std;
int n, m, dp[1005][1005];
string s, t;
int main() {
cin >> s >> t;
n = s.size(), 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] << '\n';
return 0;
}

Юунд хэрэгтэй вэ?

Хоёр string-ийг харьцуулдаг олимпиадын бодлогуудын суурь. ДНХ-ийн дараалал харьцуулах, хоёр файлын ялгааг олох программууд ийм аргаар ажилладаг. HackerRank дээрх "Common Child" бодлого яг энэ.

Яаж ажилладаг вэ?

1. State: dp[i][j] нь s-ийн эхний i үсэг ба t-ийн эхний j үсгийн хамгийн урт нийтлэг дэд дараалал. Мөр 0 ба багана 0 бүгд 0. 2. s[i − 1] = t[j − 1] бол: dp[i][j] = dp[i − 1][j − 1] + 1. 3. Өөр бол аль нэг үсгийг хаяна: dp[i][j] = max(dp[i − 1][j], dp[i][j − 1]). 4. Хариу нь dp[n][m]. Оролт: хоёр мөрөнд s ба t string.

Яагаад зөв, хэр хурдан бэ?

Сүүлийн хоёр үсэг ижил бол тэдгээрийг хослуулахаас алдах юм байхгүй, үлдсэн хэсэг нь dp[i - 1][j - 1]. Өөр бол хамгийн сайн хариунд s-ийн сүүлийн үсэг эсвэл t-ийн сүүлийн үсэг ашиглагдахгүй. Тиймээс хоёр сонголтын их нь зөв.

n · m нүд, тус бүрийг O(1)-д бодно: хугацаа ба санах ой O(n · m). n = m = 1000 бол сая нүд. n = m = 5000 бол 25 сая нүд, хугацаа хүрэлцэнэ, харин int хүснэгт 100 MB орчим болно.

Түгээмэл алдаа

  • String-ийн index-ийг хүснэгтийнхтэй андуурах. dp[i][j]-д s[i - 1], t[j - 1]-ийг харьцуулна.
  • Substring-тэй андуурах. Энэ код зэргэлдээ байх албагүй дэд дараалал олно.
  • Хүснэгтийг local хувьсагч болгох. dp[1005][1005] main дотор stack-ийг дүүргэж болно, global болго.

Хязгаарын тохиолдол

  • Нийтлэг үсэг огт байхгүй: бүх нүд 0, хариу 0.
  • Хоёр string ижил: хариу нь string-ийн урт.
  • Нэг нь нөгөөгийнхөө дэд дараалал: хариу нь богино string-ийн урт.

Өөрийгөө шалга

  1. "HELLO" ба "YELLOW"-ийн LCS хэд вэ?

    Хариу харах

    4: ELLO.

  2. "ABC" ба "XYZ"-ийн хариу хэд вэ?

    Хариу харах

    0.

  3. Хоёр үсэг ижил үед аль нүдийг уншдаг вэ?

    Хариу харах

    Зүүн дээд нүд dp[i - 1][j - 1]-ийг уншаад 1 нэмнэ.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1."AXBY" ба "ABXY"-ийн хүснэгтийг бөглөөд хариуг ол.

    Hint харах

    4×4 хүснэгт, мөр 0 ба багана 0 нь 0.

    Хариу ба тайлбар

    Хариу 3, жишээ нь AXY эсвэл ABY.

  2. 2.Уртыг нь биш, LCS-ийг өөрийг нь хэвлэдэг болго.

    Hint харах

    dp[n][m]-ээс эхлээд хүснэгтээр буцаж алх.

    Хариу ба тайлбар

    i, j > 0 үед: үсэг ижил бол тэр үсгийг хадгалаад i--, j--. Өөр бол dp[i - 1][j] >= dp[i][j - 1] үед i--, үгүй бол j--. Хадгалсан үсгүүдийг урвуу дарааллаар хэвлэнэ.

  3. 3.String-ийн хамгийн урт palindrome дэд дарааллыг LCS-ээр ол.

    Hint харах

    Palindrome урдаасаа ч, ардаасаа ч ижил уншигдана.

    Хариу ба тайлбар

    Хариу нь LCS(s, reverse(s)). "BBABCBCAB" бол 7, жишээ нь BABCBAB.

Жишээ

Оролт

ABCBDA
BDCABA

Гаралт

4

Одоо өөрөө бодоод үз

Бодлого

Хичээл

Энэ сэдвийн хичээл удахгүй нэмэгдэнэ.