作者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
※ alan23273850:转录至看板 Math 04/29 13:52
1F：推 LPH66: Manacher 的线性是整体时间喔 04/29 14:06
2F：→ alan23273850: 我知道啊！我是想问我的方法有没有办法也一样优化到 04/29 14:07
3F：→ alan23273850: 跟 Manacher's 一样的线性时间 04/29 14:07
4F：推 ddavid: 你这问题不就是要维护的字串数量最坏情况跟n有关吗，除非 04/29 16:34
5F：→ ddavid: 你能把维护字串数量压到常数才可能变成O(n)啊 04/29 16:34
6F：→ alan23273850: 换句话说，我必须每遇到一个新字元就能马上判断新开 04/29 18:17
7F：→ alan23273850: 始的字串的最大可能长度是否会超越目前累积的字串长 04/29 18:17
8F：→ alan23273850: 这也太困难了吧！ 04/29 18:18
9F：推 ddavid: 所以Manacher才高明啊 04/30 00:37
10F：→ diabolica: 好猛 05/05 12:43