Python - Tìm chuỗi con chung dài nhất (Dynamic Programming Bottom-Up)

Bài toán: Tìm chuỗi con chung dài nhất (Longest Common Substring - LCS) của hai chuỗi sử dụng quy hoạch động (Dynamic Programming) tiếp cận Bottom-Up.

Khác với Subsequence (không cần liên tiếp), Substring yêu cầu các ký tự liền kề trong cả hai chuỗi.

Thuật toán Bottom-Up DP

Tạo bảng DP kích thước (m+1) × (n+1) với m = len(s1), n = len(s2).

dp[i][j] = độ dài chuỗi con chung kết thúc tại s1[i-1] và s2[j-1].

Ví dụ

def longest_common_substring(s1, s2):
    """
    Tìm chuỗi con chung dài nhất (Bottom-Up DP).
    
    Returns:
        tuple: (length, substring, start_index_s1, start_index_s2)
    """
    m, n = len(s1), len(s2)
    
    # Bảng DP: (m+1) x (n+1), khởi tạo 0
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    max_len = 0
    end_pos = 0  # Vị trí kết thúc trong s1
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                if dp[i][j] > max_len:
                    max_len = dp[i][j]
                    end_pos = i
            else:
                dp[i][j] = 0  # Không liên tiếp -> reset 0
    
    if max_len == 0:
        return 0, "", -1, -1
    
    start = end_pos - max_len
    return max_len, s1[start:end_pos], start, end_pos - 1

# Test
s1 = 'bull'
s2 = 'bullied'

length, substring, i1, i2 = longest_common_substring(s1, s2)

print(f"Chuỗi 1: '{s1}'")
print(f"Chuỗi 2: '{s2}'")
print(f"\nĐộ dài LCS: {length}")
print(f"Chuỗi con chung: '{substring}'")
print(f"Vị trí trong s1: [{i1}:{i2}]")

Kết quả

Chuỗi 1: 'bull'
Chuỗi 2: 'bullied'

Độ dài LCS: 4
Chuỗi con chung: 'bull'
Vị trí trong s1: [0:3]

Giải thích

• Bảng DP lưu độ dài chuỗi con chung kết thúc tại mỗi cặp vị trí.
• Nếu s1[i-1] == s2[j-1]: mở rộng từ chéo trên-trái dp[i-1][j-1] + 1.
• Nếu khác: dp[i][j] = 0 (substring yêu cầu liên tiếp).
• Theo dõi max_len và end_pos để lấy substring.

Tối ưu không gian: O(min(m,n))

def lcs_optimized(s1, s2):
    """Tối ưu bộ nhớ: chỉ giữ 2 hàng."""
    if len(s1) < len(s2):
        s1, s2 = s2, s1  # s1 dài hơn
    
    m, n = len(s1), len(s2)
    prev = [0] * (n + 1)
    curr = [0] * (n + 1)
    
    max_len = 0
    end_pos = 0
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                curr[j] = prev[j - 1] + 1
                if curr[j] > max_len:
                    max_len = curr[j]
                    end_pos = i
            else:
                curr[j] = 0
        prev, curr = curr, prev  # Swap
    
    if max_len == 0:
        return ""
    return s1[end_pos - max_len:end_pos]

print(lcs_optimized('bull', 'bullied'))  # 'bull'

Tìm TẤT CẢ chuỗi con chung dài nhất (có thể nhiều)

def all_longest_common_substrings(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    max_len = 0
    results = set()
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                if dp[i][j] > max_len:
                    max_len = dp[i][j]
                    results = {s1[i - max_len:i]}
                elif dp[i][j] == max_len and max_len > 0:
                    results.add(s1[i - max_len:i])
    
    return max_len, results

print(all_longest_common_substrings('abcabc', 'abc'))  # (3, {'abc'})
print(all_longest_common_substrings('abab', 'baba'))   # (3, {'aba', 'bab'})

Độ phức tạp

• Thời gian: O(m × n)
• Không gian: O(m × n) (hoặc O(min(m,n)) tối ưu)