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

Trong lĩnh vực lập trình, vấn đề tìm kiếm xâu con đối xứng dài nhất là một trong những thách thức mà nhiều lập trình viên gặp phải. Xâu con đối xứng được định nghĩa là một chuỗi các ký tự mà chuỗi đó không thay đổi khi đọc ngược lại, chẳng hạn như "radar" hoặc "level". Giải quyết vấn đề này yêu cầu cài đặt một thuật toán hiệu quả để tìm và trả về xâu con đối xứng dài nhất có trong một chuỗi cho trước.

Một trong những giải pháp phổ biến và hiệu quả cho bài toán này là sử dụng thuật toán Manacher, một thuật toán có độ phức tạp thời gian O(n). Tuy nhiên, để dễ hiểu, chúng ta sẽ bắt đầu bằng giải pháp đơn giản hơn và sau đó tiến tới các phương pháp tối ưu hơn.

Phương pháp kiểm tra tất cả xâu con

Phương pháp đơn giản nhất là kiểm tra tất cả các xâu con của chuỗi ban đầu và xác định xem xâu nào là đối xứng. Sau đó, chúng ta lưu trữ và so sánh để tìm ra xâu đối xứng dài nhất.

def is_palindrome(s):
    return s == s[::-1]

def longest_palindromic_substring(s):
    n = len(s)
    if n == 0:
        return ""
    longest = s[0]
    for i in range(n):
        for j in range(i + 1, n + 1):
            sub_str = s[i:j]
            if is_palindrome(sub_str) and len(sub_str) > len(longest):
                longest = sub_str
    return longest

Phương pháp mở rộng từ trung tâm

Một phương pháp khác tối ưu hơn và dễ cài đặt là mở rộng từ trung tâm (Expand Around Center). Phương pháp này dựa trên quan sát rằng một xâu đối xứng sẽ có một hoặc hai ký tự làm trung tâm (cho các xâu có độ dài lẻ và chẵn).

def expand_around_center(s, left, right):
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    return s[left + 1:right]

def longest_palindromic_substring(s):
    n = len(s)
    if n == 0:
        return ""
    longest = ""
    for i in range(n):
        # Kiểm tra xâu đối xứng có độ dài lẻ
        odd_palindrome = expand_around_center(s, i, i)
        if len(odd_palindrome) > len(longest):
            longest = odd_palindrome
        # Kiểm tra xâu đối xứng có độ dài chẵn
        even_palindrome = expand_around_center(s, i, i + 1)
        if len(even_palindrome) > len(longest):
            longest = even_palindrome
    return longest

Thuật toán Manacher

Thuật toán Manacher là phương pháp tối ưu nhất cho bài toán với độ phức tạp O(n), nhờ vào việc tối ưu hóa quá trình kiểm tra bằng cách sử dụng một mảng hỗ trợ.

def longest_palindromic_substring(s):
    T = '#'.join(f'^{s}$')
    n = len(T)
    L = [0] * n
    C = R = 0
    for i in range(1, n - 1):
        L[i] = (R > i) and min(R - i, L[2 * C - i])
        while T[i + L[i] + 1] == T[i - L[i] - 1]:
            L[i] += 1
        if i + L[i] > R:
            C, R = i, i + L[i]
    max_len, center_index = max((n, i) for i, n in enumerate(L))
    return s[(center_index - max_len) // 2: (center_index + max_len) // 2]

# Ví dụ sử dụng
s = "babad"
print(longest_palindromic_substring(s))  # Kết quả có thể là "bab" hoặc "aba"

Tóm lại

Việc tìm kiếm xâu con đối xứng dài nhất trong lập trình có thể được giải quyết bằng nhiều phương pháp khác nhau, từ đơn giản đến phức tạp. Tùy thuộc vào yêu cầu cụ thể về hiệu suất và độ phức tạp, bạn có thể lựa chọn phương pháp kiểm tra tất cả xâu con, phương pháp mở rộng từ trung tâm hay sử dụng thuật toán Manacher để đạt được kết quả mong muốn. Qua bài viết này, hy vọng bạn sẽ nắm được kiến thức cần thiết để cài đặt thuật toán tìm kiếm xâu con đối xứng dài nhất một cách hiệu quả.