作者FRAXIS (喔喔)
看板Prob_Solve
标题[问题] 回文树/回文自动机
时间Sun Aug 16 06:21:15 2015
最近在研究最小回文分割问题
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://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1439677281.A.388.html
※ 编辑: FRAXIS (76.118.43.187), 08/16/2015 06:22:06