Manacher 算法分析与实现
最近刚做完 Leetcode 上的 Longest Palindromic Substring,用的是 Manacher 算法(国内俗称马拉车算法)。之前高中打 OI 时也做过同样的题目,不过当时是作为动态规划的例题来介绍的;再加上后来我没认真学 Manacher 算法,所以直到这几天才算是初步学习了该算法。
Manacher 算法是一种能以 O(n) 的时间复杂度找出一个字符串里的所有回文子串的算法。相比于暴力搜索(O(n^3))与动态规划/中心扩展(O(n^2)),它的时间复杂度要低得多。这篇博客就简单记录一下我对 Manacher 算法的理解。