算法

Tecker Yu

2 minute read

manacher 俗称马拉车算法,也是本文的主角,是一种能够将最长回文串的求解复杂度降低到 O(N) 的一种高效算法, 当我第一次见到求解最长回文串的题目时,首先采用的就是暴力解法,O(N平方) 复杂度遍历所有可能的串,然后再用 O(N) 的时间来求回文串的最大长度,使用 map 存储各个下标对的回文情况尽管能减少一部分计算, 但是显然这种方式时间复杂度过高,部分 case 容易超时