Algo Visualizedდაიწყე სწავლა

უდიდესი საერთო ქვემიმდევრობა

git diff, პლაგიატის შემმოწმებლები და დნმ-ის შედარება ერთსა და იმავეს კითხულობს: რომელია ყველაზე გრძელი მიმდევრობა, რომელიც ორივე შემავალ სტრიქონში იმავე რიგით გვხვდება? ყველა ქვემიმდევრობის გადარჩევა ექსპონენციალურია; პრეფიქსების ერთი ცხრილი პასუხს O(m·n)-ში იძლევა.

★ ლექცია: DP_LCS · ზაზა გამეზარდაშვილი▶ ვიდეო საშუალო⏱ 20 წთ

←ეყრდნობა

10დპ ბადეზეუსქ-ის ცხრილი ორი სტრიქონის პრეფიქსებზე აგებული ბადეა, რომელიც უჯრა-უჯრა ივსება.4ქვესიმრავლეებისა და გადანაცვლებების გენერაციაქვემიმდევრობა პოზიციების ქვესიმრავლეა; უსქ მათ ყველას არ ცდის.

გზას უხსნის→

10რედაქტირების მანძილირედაქტირების მანძილი იმავე ცხრილს ავსებს, რასაც უსქ, ჩასმით, წაშლითა და შეცვლით.
1ისწავლე2უყურე3ითამაშე4შეამოწმე5ივარჯიშე
01

ისწავლე

იდეა, მექანიზმი და ფასი.

01რა არის ქვემიმდევრობა

ვიტყვით, რომ მოცემული მიმდევრობიდან მივიღეთ ქვემიმდევრობა, თუ მიმდევრობის ზოგიერთი ელემენტი წავშალეთ, ხოლო დარჩენილ ელემენტებზე რიგი შენარჩუნებულია (თავად მიმდევრობაც ითვლება საკუთარ ქვემიმდევრობად).

მათემატიკური ფორმულირებით: Z = ⟨z₁, z₂, …, z_k⟩ მიმდევრობას ეწოდება X = ⟨x₁, x₂, …, x_n⟩ მიმდევრობის ქვემიმდევრობა, თუ არსებობს ინდექსთა მკაცრად ზრდადი მიმდევრობა i₁ < i₂ < … < i_k, რომლისთვისაც z_j = x_{i_j} ყველა j = 1, …, k-სთვის.

ლექციის მაგალითი: Z = ⟨B, C, D, B⟩ არის X = ⟨A, B, C, B, D, A, B⟩ მიმდევრობის ქვემიმდევრობა, ინდექსთა შესაბამისი მიმდევრობით ⟨2, 3, 5, 7⟩.

ნუ აურევ ქვესტრიქონში, რომელიც უწყვეტი უნდა იყოს. „BCD“ არ არის ABCBDAB-ის ქვესტრიქონი (შუაში B ერევა), მაგრამ ქვემიმდევრობაა. სწორედ გამოტოვების ეს თავისუფლება ხდის ამოცანას საინტერესოს.

ქვემიმდევრობა: წავშალოთ ზოგი, რიგი შევინარჩუნოთX =A1B2C3B4D5A6B7Z =BCDBინდექსები 2 < 3 < 5 < 7

02საერთო, უდიდესი და გადასარჩევად ძალიან ბევრი

ვიტყვით, რომ Z წარმოადგენს X და Y მიმდევრობების საერთო ქვემიმდევრობას, თუ Z არის როგორც X-ის, ასევე Y-ის ქვემიმდევრობა. X = ⟨A, B, C, B, D, A, B⟩ და Y = ⟨B, D, C, A, B, A⟩-სთვის ⟨B, C, A⟩ საერთოა (სიგრძე 3), მაგრამ ⟨B, C, B, A⟩ უფრო გრძელია: სიგრძე 4, და უფრო გრძელი არ არსებობს. ⟨B, D, A, B⟩-ის სიგრძეც 4-ია: უდიდესი საერთო ქვემიმდევრობა (უსქ) შეიძლება რამდენიმე იყოს.

სრული გადარჩევა X-ის ყველა ქვემიმდევრობას ჩამოწერდა და Y-ში შეამოწმებდა. m სიგრძის მიმდევრობა შეიცავს 2ᵐ ქვემიმდევრობას (იმდენივეს, რამდენ ქვესიმრავლესაც შეიცავს {1, 2, …, m}), ანუ დრო ექსპონენციალურია.

გამოსავალი პრეფიქსებშია. i სიგრძის პრეფიქსი არის Xᵢ = ⟨x₁, …, xᵢ⟩, სადაც i მოთავსებულია 0-დან m-მდე. აქ X₄ = ⟨A, B, C, B⟩, ხოლო X₀ ცარიელია. ქვეამოცანები იქნება: X-ის რომელიმე პრეფიქსისა და Y-ის რომელიმე პრეფიქსის უსქ. ასეთი მხოლოდ (m+1)(n+1)-ია.

საერთო ქვემიმდევრობა: ორივეში, იმავე რიგითXABCBDABYBDCABABCA: საერთო, 3BCBA: უდიდესი, 4BDAB: ისიც უდიდესი, 4

03თეორემა უსქ-ის აგებულების შესახებ

ვთქვათ, Z = ⟨z₁, …, z_k⟩ ერთ-ერთი უდიდესი საერთო ქვემიმდევრობაა X = ⟨x₁, …, x_m⟩ და Y = ⟨y₁, …, y_n⟩ მიმდევრობებისთვის. მაშინ:

  • თუ xₘ = yₙ, მაშინ z_k = xₘ = yₙ და Z_{k−1} წარმოადგენს უსქ-ს X_{m−1}-ისა და Y_{n−1}-ისთვის;
  • თუ xₘ ≠ yₙ და z_k ≠ xₘ, მაშინ Z წარმოადგენს უსქ-ს X_{m−1}-ისა და Y-ისთვის;
  • თუ xₘ ≠ yₙ და z_k ≠ yₙ, მაშინ Z წარმოადგენს უსქ-ს X-ისა და Y_{n−1}-ისთვის.

თეორემიდან ჩანს, რომ ორი მიმდევრობის უსქ შეიცავს მათივე პრეფიქსების უსქ-ს: ამოცანას გააჩნია ოპტიმალურობის თვისება ქვეამოცანებისთვის. უსქ-ის პოვნა დადის ან ერთი (ბოლო ასოები ტოლია: ვხსნით X_{m−1}, Y_{n−1}-ს და ასოს ვუმატებთ), ან ორი ქვეამოცანის ამოხსნაზე (განსხვავდება: ვხსნით ორივეს და ვიღებთ უდიდესს).

ადგილი აქვს ქვეამოცანების გადაფარვასაც: „X_{m−1} და Y“-საც და „X და Y_{n−1}“-საც სჭირდება „X_{m−1} და Y_{n−1}“. უბრალო რეკურსია მას ისევ და ისევ ამოხსნიდა, ამიტომ ყოველ პასუხს ცხრილში ვინახავთ.

თეორემა: შევადაროთ ბოლო ასოებიXABCBDABYBDCABAშემთხვევა 1xₘ = yₙzₖ = xₘ = yₙZₖ₋₁ = უსქ(Xₘ₋₁, Yₙ₋₁)ერთი ქვეამოცანაშემთხვევა 2xₘ ≠ yₙ, zₖ ≠ xₘZ = უსქ(Xₘ₋₁, Y)ორი ქვეამოცანიდან უკეთესიშემთხვევა 3xₘ ≠ yₙ, zₖ ≠ yₙZ = უსქ(X, Yₙ₋₁)ორი ქვეამოცანიდან უკეთესიაქ x₇ = B ≠ y₆ = A → ვიღებთ 2-ისა და 3-ის უდიდესს

04რეკურენტული თანაფარდობა და ცხრილი

c[i, j]-ით აღვნიშნოთ უსქ-ის სიგრძე Xᵢ და Yⱼ მიმდევრობებისთვის. თუ i ან j ტოლია 0-ის, მაშინ ორი მიმდევრობიდან ერთ-ერთი ცარიელია და c = 0. სხვა შემთხვევაში:

  • c[i, j] = c[i−1, j−1] + 1, თუ xᵢ = yⱼ;
  • c[i, j] = max(c[i−1, j], c[i, j−1]), თუ xᵢ ≠ yⱼ.

(m+1) × (n+1) ცხრილს ვავსებთ სტრიქონ-სტრიქონ; ყოველ უჯრას მხოლოდ ზედა, მარცხენა და ზედა მარცხენა მეზობლები სჭირდება, რომლებიც უკვე შევსებულია. ლექცია პირველი სტრიქონით იწყება: X[1] = A ≠ Y[1] = B, ამიტომ c[1][1] = max(c[0][1], c[1][0]) = 0; ასევე Y[2]-სა და Y[3]-ზე; შემდეგ X[1] = Y[4] = A, ამიტომ c[1][4] = c[0][3] + 1 = 1.

როცა 42-ვე შიდა უჯრა შეივსება, ქვედა მარჯვენა კუთხე c[7][6] = 4 მთელი მიმდევრობების უსქ-ის სიგრძეა. თითოეული უჯრის შესავსებად საჭიროა O(1) ოპერაცია, ამიტომ შევსება O(m·n) ღირს.

c[i][j] = უსქ-ის სიგრძე Xᵢ და Yⱼ პრეფიქსებისთვისBDCABA1 A2 B3 C4 B5 D6 A7 B00000000000111011112201122220112233012223301223340122344ტოლი ასოები: ↖ და ვიღებთსხვა: უდიდესი მეზობელი(ტოლობისას ↑)უსქ =B C B AX = ABCBDAB, Y = BDCABA
ფერადი უჯრები კუთხიდან უკან სვლაა; მწვანეები ასოს იძლევა.

05უსქ-ის აღდგენა და ასიმპტოტიკა

ცხრილი სიგრძეს გვაძლევს; თავად მიმდევრობა c[m][n]-დან უკან სვლით მიიღება:

  • თუ xᵢ = yⱼ, ეს ასო უსქ-შია: ვწერთ მას და დიაგონალზე, (i−1, j−1)-ზე გადავდივართ;
  • სხვა შემთხვევაში გადავდივართ ზედა და მარცხენა მეზობლებიდან უდიდესზე.

ასოები უკუღმა გამოდის, ამიტომ ბოლოს თავიდან წავიკითხოთ. ყოველ ბიჯზე ან i მცირდება, ან j, ან ორივე ერთად, ამიტომ საშედეგო მიმდევრობის აღდგენას დასჭირდება O(m + n).

ტოლობას მნიშვნელობა აქვს. თუ ტოლობისას ზემოთ მივდივართ (როგორც სლაიდებზე), ვიღებთ BCBA-ს; ლექციის C++ კოდი იყენებს if (arr[i−1][j] > arr[i][j−1]) i--; else j--;-ს, ანუ ტოლობისას მარცხნივ მიდის და პოულობს BDAB-ს. ორივე სწორია: ერთი სიგრძის სხვადასხვა უსქ.

ცხრილისთვის მეხსიერება O(m·n)-ია. თუ მხოლოდ სიგრძე გჭირდება, ორი სტრიქონი საკმარისია. და შეადარე: ორი 20 სიგრძის სტრიქონისთვის 441 უჯრაა, სრულ გადარჩევას კი 2²⁰ ≈ მილიონი ქვემიმდევრობა სჭირდება.

ლექციის C++ კოდიC++

მე-17 სლაიდი: ორმაგი ციკლი arr ცხრილს ავსებს, შემდეგ while ციკლი arr[m][n]-დან უკან მიდის და თავად ქვემიმდევრობას აღადგენს, თანხვედრილ სიმბოლოებს სათითაოდ აგროვებს.

#include <bits/stdc++.h>
using namespace std;
void lcs(string S1, string S2, int m, int n) {
    int arr[m + 1][n + 1];
    for (int i = 0; i <= m; i++) {
        for (int j=0; j <= n; j++) {
            if (i==0 || j==0) arr[i][j] = 0;
            else if (S1[i-1]==S2[j-1]) arr[i][j]=arr[i-1][j-1]+1;
            else arr[i][j]=max(arr[i-1][j], arr[i][j-1]);
        }
    }
    int index = arr[m][n], i = m, j = n;
    char lcs[index + 1];
    lcs[index] = '\0';
    while (i > 0 && j > 0) {
        if (S1[i - 1] == S2[j - 1]) {
            lcs[index - 1] = S1[i - 1];
            i--;   j--;    index--;
        }
        else if (arr[i - 1][j] > arr[i][j - 1]) i--;
        else j--;
    }
    cout<<"S1: "<<S1<<"\nS2: "<<S2<<"\nLCS: "<<lcs<<"\n";
}
int main() {
    string S1 = "ACADB";  string S2 = "ACBDAB";
    int m = S1.size();  int n = S2.size();
    lcs(S1, S2, m, n);
}

ფასი ერთი შეხედვით

ცხრილის შევსებაO(m·n)
ერთი უსქ-ის აღდგენაO(m + n)
მხოლოდ სიგრძე, ორი სტრიქონიO(min(m, n)) memory
სრული გადარჩევაO(2ᵐ · n)

დაიმახსოვრე

  1. ქვეამოცანები პრეფიქსების წყვილებია: c[i][j] = Xᵢ-ისა და Yⱼ-ის უსქ-ის სიგრძე, საზღვარზე 0.
  2. შეადარე ბოლო ასოები: ტოლია, ესე იგი დიაგონალი + 1; განსხვავდება, ესე იგი ზედა და მარცხენა უჯრების max.
  3. კუთხიდან უკან სვლით ერთ უსქ-ს O(m + n)-ში ვაღდგენთ; ტოლობის წესი წყვეტს, რამდენიმე უსქ-დან რომელს მივიღებთ.
02

უყურე

ლექცია ვიდეოს სახით.

▶

ლექცია, ანიმაციით

ვიდეო ლექციას სლაიდ-სლაიდ მიჰყვება: იგივე მაგალითი, იგივე აღნიშვნები. უყურე ვიზუალიზატორთან თამაშამდე ან მის შემდეგ.

▶ ვიდეოს გვერდი▣ პრეზენტაციად გახსნა
03

ითამაშე

გაიარე ალგორითმი ბიჯ-ბიჯ, მერე სცადე შენს მონაცემებზე.

👀 რას უყურო: ნაგულისხმევი გაშვება ლექციის X = ABCBDAB, Y = BDCABA-ა. უყურე, როგორ იღებს ყოველი უჯრა ↖-ს დამთხვევისას ან ↑ / ←-დან უდიდესს, შემდეგ კი უკან სვლა B C B A-ს წერს. სცადე ლექციის კოდის წყვილი ACADB / ACBDAB.

ინტერაქტიული ვიზუალიზატორიაქ დააწკაპე, მერე space ← →
✎ შენი მონაცემებიორი სიტყვა, თითო 9 ასომდე, მაგ. ACADB და ACBDAB (ლექციის კოდის მაგალითი).

დპ ცხრილი: X = ABCBDAB, Y = BDCABA

i\\j01:B2:D3:C4:A5:B6:A
00000000
1:A0······
2:B0······
3:C0······
4:B0······
5:D0······
6:A0······
7:B0······

უსქ (LCS)

(ჯერ ცარიელია)
საბაზისო შემთხვევა: 0-ური სტრიქონი და სვეტი 0-ია, რადგან ცარიელ პრეფიქსს საერთო არაფერი აქვს.

ფსევდოკოდი

 1 c[i][0] = c[0][j] = 0   // empty prefix 2 for i in 1..m: for j in 1..n: 3   if X[i] == Y[j]: 4     c[i][j] = c[i-1][j-1] + 1      // ↖ 5   else: 6     c[i][j] = max(c[i-1][j], c[i][j-1])  // ↑ or ← 7 reconstruct: follow arrows from c[m][n]
1 / 1
04

შეამოწმე

სამი კითხვა. აირჩიე პასუხი და ნახე ახსნა.

№1

X = ABCB, Y = BDCB. ვიცით, რომ c[3][3] = 2. რას უდრის c[4][4]?

№2

რომელია ABCBDAB-ის ქვემიმდევრობა, მაგრამ არა ქვესტრიქონი?

№3

აღდგენისას xᵢ ≠ yⱼ, ხოლო ზედა და მარცხენა მეზობლები ტოლია. რა ხდება?

05

ივარჯიშე

რეალური ამოცანები გასამყარებლად, მარტივიდან რთულისკენ.

LeetCodeLongest Common Subsequence საშუალო↗CSESLongest Common Subsequence საშუალო↗LeetCodeDelete Operation for Two Strings საშუალო↗LeetCodeShortest Common Supersequence მოწინავე↗