[問題] 最長回文子字串的最快演算法
看板Prob_Solve (計算數學 Problem Solving)作者alan23273850 (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
04/29 14:06, 1F
→
04/29 14:07,
3年前
, 2F
04/29 14:07, 2F
→
04/29 14:07,
3年前
, 3F
04/29 14:07, 3F
推
04/29 16:34,
3年前
, 4F
04/29 16:34, 4F
→
04/29 16:34,
3年前
, 5F
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
04/30 00:37, 9F
→
05/05 12:43, , 10F
05/05 12:43, 10F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
