作者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://www.ptt.cc/bbs/Prob_Solve/M.1619675516.A.98D.html
※ alan23273850:轉錄至看板 Math 04/29 13:52
推 LPH66: Manacher 的線性是整體時間喔 04/29 14:06
→ alan23273850: 我知道啊!我是想問我的方法有沒有辦法也一樣優化到 04/29 14:07
→ alan23273850: 跟 Manacher's 一樣的線性時間 04/29 14:07
推 ddavid: 你這問題不就是要維護的字串數量最壞情況跟n有關嗎,除非 04/29 16:34
→ ddavid: 你能把維護字串數量壓到常數才可能變成O(n)啊 04/29 16:34
→ alan23273850: 換句話說,我必須每遇到一個新字元就能馬上判斷新開 04/29 18:17
→ alan23273850: 始的字串的最大可能長度是否會超越目前累積的字串長 04/29 18:17
→ alan23273850: 這也太困難了吧! 04/29 18:18
推 ddavid: 所以Manacher才高明啊 04/30 00:37
→ diabolica: 好猛 05/05 12:43