Thuật toán Manacher

Thuật toán Manacher là một thuật toán tìm tất cả các xâu đối xứng trong xâu \(S\).

Nếu như các thuật toán “trâu” có độ phức tạp \(O(|S|^3)\) hoặc \(O(|S|^2)\) tuỳ theo cách cài đặt, thuật toán Manacher có thể giải quyết bài toán chỉ trong \(O(|S|)\).