作者alan23273850 (God of Computer Science)
看板Math
标题Fw: [问题] 最长回文子字串的最快演算法
时间Thu Apr 29 13:52:24 2021
※ [本文转录自 Prob_Solve 看板 #1WYabycD ]
作者: alan23273850 (God of Computer Science) 看板: Prob_Solve
标题: [问题] 最长回文子字串的最快演算法
时间: Thu Apr 29 13:51:52 2021
各位板友大家好，打给贺，太轧贺，小弟这边有个演算法想跟各位讨论一下，
关於最长回文子字串，有个演算法叫做 Manacher's Algorithm，最快线性演算法。
但是我自己想到的方法是由左扫到右随时维护到当下的字元仍然是回文的那些子字串，
举例来说，CDCDCDC 扫到最右边还是回文的子字串 (length > 1) 有：
CDC
CDCDC
CDCDCDC
这样的话随时记录出现过最长的回文子字串长度，还是可以得到答案，
但是我们也可以观察到任意时刻保存的字串数量以这个 pattern 来说，其实会是 i/2，
所以通通加起来的数量其实还是 O(n^2)，更甚者像 AAAAAA 这种全部都一样的 pattern
就会更多，如此一来这种方法根本省不了多少时间，也还没达到 O(n)，
那麽有没有办法针对特定的 pattern 或其他加速方法使得整体时间达到 O(n) 呢？
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.109.16.166 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1619675516.A.98D.html
※ 发信站: 批踢踢实业坊(ptt.cc)
※ 转录者: alan23273850 (140.109.16.166 台湾), 04/29/2021 13:52:24