Dãy số chung dài nhất: Python, C++ Ví dụ

Dãy số chung dài nhất là gì?

Bài toán tìm chuỗi con chung dài nhất (LCS) nghĩa là bạn sẽ được cho hai chuỗi ký tự, mẫu hoặc dãy các đối tượng. Trong hai chuỗi ký tự hoặc mẫu này, bạn cần tìm chuỗi con dài nhất có cùng thứ tự xuất hiện trong cả hai chuỗi ký tự hoặc mẫu.

Ví dụ

Ví dụ, có hai chuỗi ký tự được cung cấp. Giả sử rằng:

Mẫu_1 = “RGBGARGA”
Mẫu_2 = “BGRARG”

• Từ mẫu pattern_1, có thể tạo ra các chuỗi như “RGB”, “RGGA”, “RGAR”. Để tạo chuỗi, bạn cần duy trì vị trí tương đối của mỗi ký tự trong chuỗi ký tự.
• Từ mẫu_2, ta có thể tạo ra các chuỗi như “BGR”, “BRAG”, “RARG”. Các chuỗi có thể được tạo ra miễn là chúng giữ nguyên vị trí tương đối của chuỗi gốc.

Thuật ngữ vị trí tương đối có nghĩa là trật tự.

Ví dụ, “BRG” là một chuỗi hợp lệ vì chữ “B” xuất hiện đầu tiên, sau đó là “R”, và cuối cùng là “G” trong chuỗi gốc pattern_2. Tuy nhiên, nếu chuỗi là “RBRG”, nó không hợp lệ, bởi vì trong chuỗi gốc (pattern_2), chữ “B” xuất hiện đầu tiên.

Chúng ta có hai lựa chọn để tìm Dãy con chung dài nhất từ ​​hai dãy hoặc mảng đã cho.

• Phương pháp ngây thơ
• Giải pháp lập trình động: Chuỗi chung dài nhất còn được gọi là LCS.

Giải pháp đơn giản có độ phức tạp về thời gian lớn hơn và không phải là giải pháp tối ưu. Bằng cách sử dụng Giải pháp Lập trình Động (DP), chúng ta khắc phục được vấn đề về độ phức tạp.

Phương pháp ngây thơ

Phương pháp đơn giản (Naive method) là cách tiếp cận dễ dàng đối với vấn đề, bất kể độ phức tạp về thời gian và các yếu tố tối ưu hóa khác. Nó bao gồm "phương pháp vét cạn", nhiều vòng lặp và các lời gọi đệ quy trong hầu hết các trường hợp. Thuật ngữ "vét cạn" có nghĩa là xem xét tất cả các mẫu có thể có cho một vấn đề nhất định.

Ví dụ

Từ ví dụ trên về mẫu1 và mẫu2, chúng ta giả sử mẫu1 có chiều dài m và mẫu2 có chiều dài n. Để kiểm tra mọi trường hợp có thể xảy ra, chúng ta cần đánh giá mọi dãy con có thể có của mẫu 1 bằng mẫu 2.

Đây là một chuỗi ký tự đơn giản gồm 4 chữ cái “ABCD”. Ví dụ, chúng ta cần tạo một dãy từ “ABCD”. Chúng ta có thể chọn lấy một ký tự hoặc không. Điều đó có nghĩa là, với mỗi ký tự, chúng ta có hai lựa chọn:

• Ký tự sẽ được thêm vào phần tiếp theo.
• Ký tự sẽ không được thêm vào dãy sau.

Ở đây, hình ảnh hiển thị tất cả các chuỗi mà chúng ta có thể tạo từ chuỗi “ABCD”.

Chuỗi có 1 ký tự:

Chuỗi có 2 ký tự:

Chuỗi có 3 ký tự:

Từ sơ đồ trên, có 14 dãy. Nếu ta không lấy bất kỳ chữ cái nào, về cơ bản là một chuỗi rỗng, thì tổng số dãy sẽ là 15. Hơn nữa, chính chuỗi “ABCD” cũng là một dãy. Vì vậy, tổng số dãy là 16.

Vì vậy, có thể tạo ra 2^4 hoặc 16 chuỗi con từ “ABCD”. Sau đó, một chuỗi có độ dài là m sẽ có tổng số dãy con là 2^m.

Với mỗi chuỗi con, chúng ta cần kiểm tra toàn bộ mẫu2. Việc này sẽ mất thời gian O(n). O(n) là độ phức tạp của hàm tính toán thời gian thực thi.

Vì vậy, độ phức tạp thời gian tổng thể trở thành O(n*2^m). Ví dụ như trên, ta có giá trị của m=8 và n=5.

Dưới đây là các bước của Phương pháp Naive:

Bước 1) Lấy một chuỗi từ mẫu 1.
Bước 2) Hãy ghép chuỗi từ bước 1 với mẫu 2.
Bước 3) Nếu trùng khớp thì lưu chuỗi tiếp theo.
Bước 4) Nếu vẫn còn các chuỗi trong mẫu 1, hãy quay lại bước 1.
Bước 5) In dãy con dài nhất.

Cấu trúc tối ưu

Thuật ngữ "cấu trúc con tối ưu" có nghĩa là có thể tìm ra giải pháp tối ưu bằng cách giải các bài toán con. Ví dụ, trong ví dụ trên, chúng ta có mẫu 1 và mẫu 2.

Bước 1) Lấy hai ký tự đầu tiên từ mỗi mẫu.

Bước 2) Lấy ký tự thứ ba đến thứ năm từ mỗi mẫu.

Bước 3) Tiếp tục tương tự với các ký tự còn lại.

Cấu trúc đệ quy của bài toán LCS

Chúng ta tìm LCS (Common Score) trên chuỗi con (chuỗi được tạo ra từ chuỗi gốc). Sau đó, chúng ta ghi lại độ dài của LCS của các chuỗi con đó.

Bây giờ, đây là một tính chất thú vị khác đó là trùng lặpping vấn đề phụMột vấn đề được cho là có sự chồng chéo.ping Các bài toán con nếu đề bài có thể được chia thành các bài toán con nhỏ và được sử dụng nhiều lần trong chương trình.

Sơ đồ dưới đây cho thấy thuật toán đệ quy đã gọi hàm có cùng tham số nhiều lần.

Ví dụ, hãy nhìn vào cây đệ quy. Trong ô màu đậm, bạn có thể nhận thấy sự chồng chéo.ping các vấn đề con. (“RG”, “RA”), (“RG”, “R”) và các vấn đề khác được gọi nhiều lần.

Để tối ưu hóa điều này, chúng ta có phương pháp tiếp cận như sau: Lập trình năng động (ĐP).

Phương pháp đệ quy tìm dãy con chung dài nhất

Đồ thị ở trên minh họa phương pháp đệ quy. Mỗi hàm đệ quy đều có một trường hợp cơ sở để thoát khỏi vòng lặp đệ quy hoặc bắt đầu trả về từ ngăn xếp của nó.

Để thực hiện việc này, chúng ta sẽ sử dụng trường hợp cơ bản. Vì vậy, thuật toán giống như sau:

• Nếu tất cả các phần tử trước phần tử cuối cùng đều trùng khớp, thì tăng độ dài lên một và quay lại.
• Truyền hai mẫu vào hàm và lấy giá trị lớn nhất trong các giá trị trả về.
• Nếu một mẫu có độ dài bằng 0 thì chúng ta không có chuỗi con nào để so sánh. Trả về XNUMX trong trường hợp này. Đây là trường hợp cơ bản của đệ quy.

Biệt danh Code:

def lcs:
    input: pattern_1, pattern_2, len_1, len_2
    if len_1 or len_2 is zero:
        return 0
    if pattern_1[len_1 - 1] equals pattern_2[len_2 - 1]:
        return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1)
    else:
        return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2),
                   lcs(pattern_1, pattern_2, len_1, len_2 - 1))

Triển khai tại C++

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int lcs(string pattern_1, string pattern_2, int len_1, int len_2) {
  if (len_1 == 0 || len_2 == 0)
    return 0;
  if (pattern_1[len_1 - 1] == pattern_2[len_2 - 1]) {
    return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1);
  } else {
    return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2), lcs(pattern_1, pattern_2, len_1, len_2 - 1));
  }
}
int main() {
  string pattern_1, pattern_2;
  pattern_1 = "RGBGARGA";
  pattern_2 = "BGRARG";
  cout<<"Length of LCS is: "<<lcs(pattern_1, pattern_2, pattern_1.size(), pattern_2.size())<<endl;
}

Đầu ra:

Length of LCS is: 5

Triển khai tại Python

def lcs(pattern_1, pattern_2, len_1, len_2):
    if len_1 == 0 or len_2 == 0:
        return 0
    if pattern_1[len_1 - 1] == pattern_2[len_2 - 1]:
        return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1)
    else:
        return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2),
                   lcs(pattern_1, pattern_2, len_1, len_2 - 1))

pattern_1 = "RGBGARGA"
pattern_2 = "BGRARG"
print("Length of LCS is: ", lcs(pattern_1, pattern_2, len(pattern_1), len(pattern_2)))

Đầu ra:

Length of LCS is:  5

Phương pháp lập trình động tìm dãy con chung dài nhất (LCS)

Lập trình động nghĩa là tối ưu hóa phương pháp đệ quy thông thường. Ví dụ, nếu nhìn vào đồ thị của phương pháp đệ quy hoặc phương pháp đơn giản, ta có thể thấy có nhiều lời gọi hàm giống hệt nhau. Phương pháp lập trình động ghi lại tất cả các phép tính vào một mảng và sử dụng lại chúng khi cần thiết.

Chúng ta sẽ sử dụng một mảng 2 chiều có kích thước mxn, trong đó m và n là độ dài của mẫu 1 và mẫu 2. Đối với một mảng 2D, chúng ta có thể sử dụng cấu trúc dữ liệu Danh sách trong Python hoặc cấu trúc dữ liệu vectơ/mảng trong C++.

Biệt danh Code Đối với LCS sử dụng DP:

LCS(pattern_1, pattern_2):
    m = length of pattern_1 + 1
    n = length of pattern_2 + 1
    dp[n][m]
    for i in range 0 to n + 1:
        for j in range 0 to m + 1:
            if i or j equals to 0:
                dp[i][j] = 0
            else if pattern_1[i] == pattern_2[j]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[n][m]

Đây là bảng LCS được sử dụng làm cấu trúc dữ liệu mảng 2D cho phương pháp lập trình động.

Chúng ta hãy cùng thảo luận về logic mà chúng ta đã sử dụng ở đây. Các bước như sau:

Bước 1) Nếu i hoặc j bằng 0, ta lấy một chuỗi rỗng từ hai chuỗi đã cho và cố gắng tìm các chuỗi con chung. Tuy nhiên, vì chuỗi con ta lấy là chuỗi rỗng, nên độ dài của chuỗi con là 0.

Bước 2) Nếu hai ký tự trùng khớp, chúng ta sẽ gán giá trị cho chỉ số (i,j) bằng cách tăng LCS đã tính toán trước đó, LCS này nằm ở chỉ số (i-1,j-1) (từ hàng trước).

Bước 3) Nếu không khớp, ta sẽ lấy LCS lớn nhất của hai chỉ số liền kề. Và bằng cách này, ta cần điền đầy đủ các giá trị vào mảng 2D.

Bước 4) Cuối cùng, chúng ta sẽ trả về giá trị của ô cuối cùng của mảng 2D.

Về cơ bản, tất cả các giá trị trong mảng 2D đều chứa độ dài của các dãy con chung. Trong số đó, ô cuối cùng chứa độ dài của dãy con chung dài nhất.

Triển khai tại C++

#include<iostream>
using namespace std;
int lcs(string pattern_1, string pattern_2) {
  int m = pattern_1.size();
  int n = pattern_2.size();
  // dp will store solutions as the iteration goes on
  int dp[n + 1][m + 1];
  for (int i = 0; i < n + 1; i++) {
    for (int j = 0; j < m + 1; j++) {
      if (i == 0 || j == 0) {
        dp[i][j] = 0;
      } else if (pattern_2[i - 1] == pattern_1[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[n][m];
}
int main() {
  string pattern_1 = "RGBGARGA";
  string pattern_2 = "BGRARG";
  cout<<"Length of LCS: "<<lcs(pattern_1, pattern_2)<<endl;
}

Đầu ra:

Length of LCS: 5

Triển khai tại Python

def lcs(pattern_1, pattern_2):
    m = len(pattern_1)
    n = len(pattern_2)
    # dp will store solutions as the iteration goes on
    dp = [[None] * (n + 1) for item in range(m + 1)]
    for i in range(m + 1):
        for j in range(n + 1):
            if i == 0 or j == 0:
                dp[i][j] = 0
            elif pattern_1[i - 1] == pattern_2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

pattern_1 = "RGBGARGA"
pattern_2 = "BGRARG"
print("Length of LCS: ", lcs(pattern_1, pattern_2))

Đầu ra:

Length of LCS: 5

Vì vậy, cả hai chuỗi đều có dãy con chung dài nhất có độ dài 5.

Tóm lại, trong phương pháp quy hoạch động (DP), chúng ta chỉ tính toán mỗi tác vụ một lần. Trong phương pháp đệ quy, có thể xảy ra sự chồng chéo.ping các vấn đề con.

Trong Thuật toán lập trình động này, chúng tôi đang sử dụng ma trận 2D. Sẽ có hai chuỗi cho trước (giả sử cả hai đều có độ dài n). Khi đó không gian cần thiết trong mảng là nx n. Nếu chuỗi đủ lớn, chúng ta sẽ cần phiên bản giải pháp DP được tối ưu hóa bộ nhớ.

Logic đơn giản hóa được thực hiện trong mã là:

• Khai báo mảng 2D DP[m][n].
• Điền vào hàng đầu tiên và cột đầu tiên của mảng DP bằng 0.
• Lấy i và j cho lần lặp.
• Nếu pattern1[i] bằng pattern2[j], thì cập nhật DP[i][j] = DP[i-1][j-1] + 1.
• Nếu pattern1[i] không bằng pattern2[j], thì DP[i][j] sẽ là giá trị lớn nhất giữa DP[i-1][j] và DP[i][j-1].
• Tiếp tục cho đến khi i và j đạt tới m và n.
• Phần tử cuối cùng, DP[m-1][n-1], sẽ chứa độ dài.

Ở đây, nó được gọi là DP[m-1][n-1] vì chỉ số mảng bắt đầu từ 0.

Câu Hỏi Thường Gặp