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

Việc tìm kiếm chuỗi con đối xứng dài nhất trong một chuỗi ký tự là một bài toán thú vị và quan trọng trong tin học. Thuật toán Manacher là một giải pháp tối ưu để giải quyết bài toán này với độ phức tạp O(n). Trong bài viết này, chúng ta sẽ đi sâu vào việc cài đặt thuật toán Manacher trong lập trình để tìm chuỗi con đối xứng dài nhất.

Hiểu về thuật toán Manacher

Thuật toán Manacher hoạt động bằng cách xem xét từng ký tự trong chuỗi và mở rộng ra hai phía để tìm kiếm chuỗi con đối xứng tiềm năng. Thay vì chỉ làm việc trên chuỗi gốc, nó sử dụng một chuỗi thay thế được chèn thêm các ký tự đặc biệt để đơn giản hóa quá trình so sánh.

Bước 1: Chuyển đổi chuỗi

Chúng ta sẽ chuyển đổi chuỗi gốc bằng cách chèn thêm ký tự đặc biệt (ví dụ: '#') vào giữa mỗi ký tự của chuỗi gốc, và bắt đầu, kết thúc bằng ký tự đặc biệt này. Điều này giúp biến các chuỗi con đối xứng lẻ và chẵn thành một dạng chung.

def preprocess_string(s):
    return '#' + '#'.join(s) + '#'

Ví dụ, chuỗi "abba" sẽ trở thành "#a#b#b#a#".

Bước 2: Tạo bảng lưu độ dài đối xứng

Chúng ta cần một mảng P để lưu độ dài của chuỗi con đối xứng với mỗi ký tự trong chuỗi đã chuyển đổi.

def manacher_algorithm(s):
    T = preprocess_string(s)
    n = len(T)
    P = [0] * n  # Mảng lưu độ dài đối xứng
    C = R = 0  # Center và Right boundary
    
    for i in range(n):
        mirr = 2 * C - i  # Vị trí đối xứng của i qua C
        
        if i < R:
            P[i] = min(R - i, P[mirr])
        
        # Mở rộng ra hai phía
        while i + 1 + P[i] < n and i - 1 - P[i] >= 0 and T[i + 1 + P[i]] == T[i - 1 - P[i]]:
            P[i] += 1
        
        # Nếu chuỗi đối xứng vượt qua R, cập nhật C và R
        if i + P[i] > R:
            C, R = i, i + P[i]
    
    # Tìm vị trí có độ dài đối xứng lớn nhất trong mảng P
    max_len = max(P)
    center_index = P.index(max_len)
    start = (center_index - max_len) // 2  # Vị trí bắt đầu trong chuỗi gốc
    
    return s[start: start + max_len]

Cài đặt hoàn chỉnh

Dưới đây là mã nguồn Python đầy đủ cho việc tìm chuỗi con đối xứng dài nhất bằng thuật toán Manacher:

def preprocess_string(s):
    return '#' + '#'.join(s) + '#'

def manacher_algorithm(s):
    T = preprocess_string(s)
    n = len(T)
    P = [0] * n
    C = R = 0
    
    for i in range(n):
        mirr = 2 * C - i
        
        if i < R:
            P[i] = min(R - i, P[mirr])
        
        while i + 1 + P[i] < n and i - 1 - P[i] >= 0 and T[i + 1 + P[i]] == T[i - 1 - P[i]]:
            P[i] += 1
        
        if i + P[i] > R:
            C, R = i, i + P[i]
    
    max_len = max(P)
    center_index = P.index(max_len)
    start = (center_index - max_len) // 2
    
    return s[start: start + max_len]

# Ví dụ sử dụng
s = "babad"
longest_palindromic_substring = manacher_algorithm(s)
print("Chuỗi con đối xứng dài nhất là:", longest_palindromic_substring)

Kết luận

Thuật toán Manacher cung cấp một cách tiếp cận hiệu quả để tìm kiếm chuỗi con đối xứng dài nhất trong một chuỗi ký tự. Với độ phức tạp O(n), thuật toán này vượt trội hơn nhiều so với các phương pháp kiểm tra từng cặp ký tự một cách thủ công. Qua bài viết này, hy vọng bạn đã hiểu rõ hơn về cách cài đặt và ứng dụng thuật toán Manacher trong lập trình.