最近在研究最小回文分割問題 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