※ [本文轉錄自 Prob_Solve 看板 #1WYabycD ]
作者: 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
※ 發信站: 批踢踢實業坊(ptt.cc)
※ 轉錄者: alan23273850 (140.109.16.166 臺灣), 04/29/2021 13:52:24