一篇很好的 RMQ 问题的文章 - O興~

我很懒的 @ 2008-03-17 19:01

RMQ 就是 Range Minimum Query，是在一个数组中多次询问任意一个区间内的最小值的算法。在后缀数组中，求两个后缀的最长公共前缀（LCP， Longest Common Prefix）就需要用到这个算法。

我在网上找到了一篇很好的讲 RMQ 问题的文章，《Range Minimum Query and Lowest Common Ancestor》，很适合我这样初学者。其中讲了许多相关的算法，在比赛中最推荐的是 Sparse Table 算法。

标签: acm lca rmq

阅读全文(1013) / 评论 / 扔小纸条 / 给我很懒的留言 / 文件夹: program
收藏: QQ书签 del.icio.us / 订阅: Google 抓虾

最新评论

richardxx

2008-03-18 00:27 匿名 221.216.*.* 网址: http://richardxx.yo2.cn

这个翻译得不错：
http://www.cnblogs.com/drizzlecrj/archive/2007/10/23/933472.html

这个翻译我也看过了，不过我偏好看原文啦。
可别骂我臭屁啊，我只是担心翻译的人思路和原作者有出入。看原文比较保险一点。

aLLen

2008-03-18 14:14 匿名 222.66.*.*

看原文是个好习惯....
PS:机械工业一系列翻译的书就是垃圾....

是的，我见过一本机械工业的《组合数学》中文版，简直不知所云。

richardxx

2008-03-18 23:31 匿名 221.216.*.* 网址: http://richardxx.yo2.cn

但是,我始终认为第一次学一个东西的时候还是母语亲切,无论原文有多优美,翻译有多差..

评论 / 个人网页 / 扔小纸条

* 昵称
	已经注册过? 请登录新用户请先注册以便能显示头像及追踪评论回复
Email
网址
* 评论
表情
* 认证码	请输入您看到的数字 (注册登录就不用每次输入讨厌的验证码了)