[問題] 回文樹/回文自動機
看板Prob_Solve (計算數學 Problem Solving)作者FRAXIS (喔喔)時間9年前 (2015/08/16 06:21)推噓1(1推 0噓 0→)留言1則, 1人參與討論串1/1
最近在研究最小回文分割問題 http://goo.gl/ED4zLY
給定一個字串，把此字串 partition 成最少數量的回文子字串。
用 DP 可以很容易的得到一個 O(n^2) 的方法。
去年 Mikhail Rubinchik 在 codeforce 發表了新的資料結構 palindromic tree，
(http://codeforces.com/blog/entry/13959)
在他的論文裡面 (http://arxiv.org/abs/1506.04862)說用這個資料結構（Eertree）
可以在O(n lg n)的時間內解決最小回文分割問題。
想請問有沒有人曾經使用過回文樹解過這個問題，實作起來容不容易？
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 76.118.43.187
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1439677281.A.388.html
※ 編輯: FRAXIS (76.118.43.187), 08/16/2015 06:22:06
推
08/16 06:34, , 1F
08/16 06:34, 1F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
