PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] 最長回文子字串的最快演算法

看板Prob_Solve (計算數學 Problem Solving)作者 (God of Computer Science)時間3年前 (2021/04/29 13:51), 編輯推噓3(3推 0噓 7→)
留言10則, 4人參與, 最新討論串1/1
各位板友大家好，打給賀，太軋賀，小弟這邊有個演算法想跟各位討論一下， 關於最長回文子字串，有個演算法叫做 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
推
04/29 14:06, 3年前 , 1F
Manacher 的線性是整體時間喔
04/29 14:06, 1F
→
04/29 14:07, 3年前 , 2F
我知道啊！我是想問我的方法有沒有辦法也一樣優化到
04/29 14:07, 2F
→
04/29 14:07, 3年前 , 3F
跟 Manacher's 一樣的線性時間
04/29 14:07, 3F
推
04/29 16:34, 3年前 , 4F
你這問題不就是要維護的字串數量最壞情況跟n有關嗎，除非
04/29 16:34, 4F
→
04/29 16:34, 3年前 , 5F
你能把維護字串數量壓到常數才可能變成O(n)啊
04/29 16:34, 5F
→
04/29 18:17, 3年前 , 6F
換句話說，我必須每遇到一個新字元就能馬上判斷新開
04/29 18:17, 6F
→
04/29 18:17, 3年前 , 7F
始的字串的最大可能長度是否會超越目前累積的字串長
04/29 18:17, 7F
→
04/29 18:18, 3年前 , 8F
這也太困難了吧！
04/29 18:18, 8F
推
04/30 00:37, 3年前 , 9F
所以Manacher才高明啊
04/30 00:37, 9F
→
05/05 12:43, , 10F
好猛
05/05 12:43, 10F
‣ 更多 alan23273850 的文章
文章代碼(AID): #1WYabycD (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 alan23273850 的文章
文章代碼(AID): #1WYabycD (Prob_Solve)