Mô phỏng thuật toán Manacher (chuỗi con đối xứng)

Manacher Algorithm · Nhóm: Chuỗi

Manacher (chuỗi con đối xứng) (Manacher Algorithm), nhóm Chuỗi.

Mã Python

def manacher(s):
    best_l, best_r = 0, 0
    for c in range(len(s)):
        for off in (0, 1):
            l, r = c, c + off
            while l >= 0 and r < len(s) and s[l] == s[r]:
                l -= 1
                r += 1
            l, r = l + 1, r - 1
            if r - l > best_r - best_l:
                best_l, best_r = l, r
    return s[best_l:best_r + 1]

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.