×

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

Avatar of admin
admin 1 Views

Trong lĩnh vực lập trình, việc tìm kiếm chuỗi con chung dài nhất (Longest Common Substring - LCS) giữa hai chuỗi ký tự có rất nhiều ứng dụng thực tiễn, từ so sánh văn bản đến phân tích dữ liệu gene. Bài viết này sẽ hướng dẫn bạn cách cài đặt thuật toán Longest Common Substring bằng ngôn ngữ lập trình Python, nhưng cũng có thể mở rộng nguyên tắc cho các ngôn ngữ khác.

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

  1. Tạo bảng tạm thời (Dynamic Programming Table): Đầu tiên, chúng ta cần tạo ra một ma trận hai chiều để lưu trữ độ dài của các chuỗi con chung. Kích thước của ma trận này là (n+1)x(m+1), với n và m lần lượt là độ dài của hai chuỗi.

  2. Khởi tạo bảng: Ban đầu, tất cả các phần tử trong bảng đều được gán giá trị 0.

  3. Điền bảng: Chúng ta sẽ duyệt qua từng ký tự của hai chuỗi, nếu các ký tự từ hai chuỗi khớp nhau, phần tử tương ứng trong bảng sẽ được gán bằng giá trị của phần tử chéo trước đó cộng với 1. Nếu không khớp nhau, giá trị phần tử đó sẽ là 0.

  4. Tìm độ dài chuỗi con chung dài nhất: Cuối cùng, chúng ta chỉ cần tìm giá trị lớn nhất trong bảng, đây chính là độ dài của chuỗi con chung dài nhất.

Cài đặt bằng Python

Dưới đây là một ví dụ cụ thể bằng Python để minh họa quy trình trên:

def longest_common_substring(str1, str2):
    n = len(str1)
    m = len(str2)
    
    # Tạo bảng tạm thời với tất cả các phần tử bằng 0
    LCSuff = [[0] * (m + 1) for i in range(n + 1)]
    
    result = 0  # Độ dài chuỗi con chung dài nhất
    
    # Điền bảng
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if str1[i - 1] == str2[j - 1]:
                LCSuff[i][j] = LCSuff[i - 1][j - 1] + 1
                result = max(result, LCSuff[i][j])
            else:
                LCSuff[i][j] = 0
    
    return result

# Ví dụ chạy chương trình
str1 = "abcdef"
str2 = "zcdemf"
print("Độ dài chuỗi con chung dài nhất là:", longest_common_substring(str1, str2))

Giải thích

  • Chúng ta khởi tạo một bảng LCSuff với kích thước (n+1)x(m+1) để lưu trữ độ dài các chuỗi con chung.
  • Biến result sẽ lưu trữ độ dài của chuỗi con chung dài nhất tìm thấy.
  • Hai vòng lặp lồng nhau duyệt qua từng ký tự của hai chuỗi. Nếu các ký tự khớp nhau, giá trị của phần tử tương ứng trong bảng LCSuff được cập nhật. Nếu không, giá trị đó sẽ là 0.

Ứng dụng và Nhược điểm

Thuật toán này có thời gian thực hiện và mức sử dụng bộ nhớ là O(n*m), nơi n và m là độ dài của hai chuỗi. Mặc dù thời gian thực hiện này là chấp nhận được đối với chuỗi ngắn và vừa, nhưng có thể trở thành vấn đề đối với chuỗi rất dài.

Thuật toán Longest Common Substring là một công cụ mạnh mẽ trong các lĩnh vực phân tích văn bản, sinh học tính toán, và nhiều ứng dụng khác. Việc nắm vững cách cài đặt thuật toán này không chỉ giúp bạn tối ưu hóa quá trình xử lý dữ liệu mà còn mở ra nhiều cơ hội trong nghiên cứu và phân tích.

Hy vọng bài viết này cung cấp cho bạn một cái nhìn toàn diện về cách cài đặt và ứng dụng thuật toán này trong thực tiễn.

Comments

Bài viết liên quan