หา Longest Common Substring ด้วย Dynamic Programming (Bottom-Up) ใน Python

บทนำ

Longest Common Substring (LCS) คือ substring ที่ยาวที่สุดที่ปรากฏในทั้งสองสตริง วิธี Dynamic Programming แบบ Bottom-Up สร้างตาราง DP เก็บความยาว substring ที่ลงท้ายที่ตำแหน่ง i, j

ตัวอย่างโค้ด

def longest_common_substring(s1, s2):
    m, n = len(s1), len(s2)
    # DP table: (m+1) x (n+1) เริ่มที่ 0
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    max_len = 0
    end_pos = 0  # ตำแหน่งจบใน 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 (เริ่มต้นเป็น 0 แล้ว)
    
    if max_len == 0:
        return ""
    return s1[end_pos - max_len : end_pos]

# ทดสอบ
s1 = 'bull'
s2 = 'bullied'
result = longest_common_substring(s1, s2)
print(f"สตริง 1: {s1}")
print(f"สตริง 2: {s2}")
print(f"Longest Common Substring: '{result}' (ความยาว {len(result)})")

ผลลัพธ์

สตริง 1: bull
สตริง 2: bullied
Longest Common Substring: 'bull' (ความยาว 4)

คำอธิบายอัลกอริทึม

1. สร้างตาราง DP ขนาด (m+1)×(n+1) เริ่มต้น 0
2. dp[i][j] = ความยาว common suffix ของ s1[:i] และ s2[:j]
3. ถ้า s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1
4. ติดตาม max_len และ end_pos ตลอด
5. ตัด substring จาก s1 ด้วยตำแหน่งที่จดไว้

ความซับซ้อน

• เวลา: O(m×n)
• พื้นที่: O(m×n) (ลดเหลือ O(min(m,n)) ได้ด้วยการเก็บแค่ 2 แถว)

ตัวอย่างเพิ่มเติม

print(longest_common_substring("abcdef", "zabcy"))   # "abc"
print(longest_common_substring("hello", "world"))    # "lo"
print(longest_common_substring("python", "java"))    # ""