×

Cài đặt thuật toán Longest Common Subsequence trong lập trình

Avatar of admin
admin 0 Views

Trong lập trình, một trong những vấn đề phổ biến trong lĩnh vực lý thuyết chuỗi và phân tích văn bản là tìm dãy con chung dài nhất (Longest Common Subsequence - LCS). LCS của hai dãy là dãy con dài nhất xuất hiện trong cả hai dãy theo cùng một thứ tự. Thuật toán LCS không yêu cầu các phần tử trong chuỗi con xuất hiện kế tiếp nhau, nhưng chúng phải xuất hiện theo đúng thứ tự.

Bước đầu tiên: Hiểu nguyên lý của LCS

Để giải quyết bài toán LCS, chúng ta cần sử dụng phương pháp lập trình động. Lập trình động giúp tối ưu hoá việc tính toán bằng cách lưu trữ kết quả của các phép tính trước đó để tránh việc tính lại những giá trị lặp đi lặp lại.

Cấu trúc bảng lưu trữ

Một trong những công cụ quan trọng khi xử lý lập trình động là bảng hai chiều, thường được biểu diễn bởi một ma trận. Giả sử ta có hai chuỗi X và Y với độ dài lần lượt là m và n. Ta sẽ sử dụng một bảng dp với kích thước (m+1) x (n+1) để lưu trữ các giá trị LCS.

Các bước cơ bản của thuật toán LCS

  1. Khởi tạo bảng dp:

    • Nếu một trong hai chuỗi là rỗng, LCS của chúng sẽ là 0. Do đó, giá trị tại hàng đầu tiên (dp[i][0]) và cột đầu tiên (dp[0][j]) đều là 0.

  2. Điền giá trị vào bảng dp:

    • Duyệt qua từng ký tự của cả hai chuỗi, từ đầu đến cuối.
    • Nếu ký tự cuối cùng của hai chuỗi con hiện tại trùng nhau, giá trị tại dp[i][j] sẽ bằng dp[i-1][j-1] + 1.
    • Nếu không trùng, giá trị tại dp[i][j] sẽ bằng giá trị lớn hơn trong hai giá trị dp[i-1][j] và dp[i][j-1].

  3. Lấy kết quả từ bảng dp:

    • Nhìn vào ô cuối cùng của bảng dp, chính là giá trị của LCS của cả hai chuỗi.

Ví dụ cụ thể

Để hiểu rõ hơn, hãy xem một ví dụ cụ thể:

Giả sử chúng ta có hai chuỗi:

  • X = "ABCBDAB"
  • Y = "BDCAB"

Chúng ta sẽ lập bảng dp có kích thước (8 x 6) (vì chiều dài của X là 7 và chiều dài của Y là 5):

      B  D  C  A  B
   0  0  0  0  0  0
A  0  0  0  0  1  1
B  0  1  1  1  1  2
C  0  1  1  2  2  2
B  0  1  2  2  2  3
D  0  1  2  2  2  3
A  0  1  2  2  3  3
B  0  1  2  2  3  4

Giá trị tại dp[7][5] là 4, do đó LCS của hai chuỗi trên là 4.

Mã nguồn cài đặt bằng Python

Dưới đây là một đoạn mã mẫu để cài đặt thuật toán LCS bằng Python:

def lcs(X, Y):
    m = len(X)
    n = len(Y)
    dp = [[0] * (n+1) for _ in range(m+1)]

    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i-1] == Y[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]

# Ví dụ sử dụng
X = "ABCBDAB"
Y = "BDCAB"
print("Độ dài LCS là", lcs(X, Y))

Thuật toán trên không chỉ mang tính ứng dụng cao mà còn giúp cải thiện hiệu suất khi xử lý các vấn đề liên quan đến chuỗi. Bằng cách lưu trữ và tái sử dụng các kết quả trung gian, phương pháp lập trình động trở thành một phương pháp mạnh mẽ và hiệu quả trong việc giải quyết bài toán LCS.

Comments

Bài viết liên quan