phoenixgel的博客

转载 Manacher算法学习（转载）

原文链接： 刘毅的网络日志 问题 给定一个字符串，输出该字符串中的最长回文子串 例如，字符串 aabac的最长回文子串是 aba; 字符串 ecddcfgf的最长回文子串为 cddc Manacher 算法说明 该算法的最大优势在于 时间复杂度为 O(n) 算法的核心是，在对字符串遍历并寻找以当前字符为中心的最大回文半径时，使用到了已经遍历过的字符的信息，这样避免了多余的遍历 代码 class Manacher { s: string; constructor(str: string) {