[问题] 最长回文子字串的最快算法

楼主: alan23273850   2021-04-29 13:51:52
各位板友大家好,打给贺,太轧贺,小弟这边有个算法想跟各位讨论一下,
关于最长回文子字串,有个算法叫做 Manacher's Algorithm,最快线性算法。
但是我自己想到的方法是由左扫到右随时维护到当下的字符仍然是回文的那些子字串,
举例来说,CDCDCDC 扫到最右边还是回文的子字串 (length > 1) 有:
CDC
CDCDC
CDCDCDC
这样的话随时记录出现过最长的回文子字串长度,还是可以得到答案,
但是我们也可以观察到任意时刻保存的字串数量以这个 pattern 来说,其实会是 i/2,
所以通通加起来的数量其实还是 O(n^2),更甚者像 AAAAAA 这种全部都一样的 pattern
就会更多,如此一来这种方法根本省不了多少时间,也还没达到 O(n),
那么有没有办法针对特定的 pattern 或其他加速方法使得整体时间达到 O(n) 呢?
作者: LPH66 (-6.2598534e+18f)   2021-04-29 14:06:00
Manacher 的线性是整体时间喔
楼主: alan23273850   2021-04-29 14:07:00
我知道啊!我是想问我的方法有没有办法也一样优化到跟 Manacher's 一样的线性时间
作者: ddavid (谎言接线生)   2021-04-29 16:34:00
你这问题不就是要维护的字串数量最坏情况跟n有关吗,除非你能把维护字串数量压到常数才可能变成O(n)啊
楼主: alan23273850   2021-04-29 18:17:00
换句话说,我必须每遇到一个新字符就能马上判断新开始的字串的最大可能长度是否会超越目前累积的字串长这也太困难了吧!
作者: ddavid (谎言接线生)   2021-04-30 00:37:00
所以Manacher才高明啊

Links booklink

Contact Us: admin [ a t ] ucptt.com