求达人详细解释Hirschberg's Algorithm（LCS问题）（以解决） - 数据结构与算法

编程论坛 → 开发语言 → 『数据结构与算法』 → 求达人详细解释Hirschberg's Algorithm（LCS问题）（以解决）

标题：求达人详细解释Hirschberg's Algorithm（LCS问题）（以解决）

只看楼主

安静的小羊

来　自：广东
等　级：新手上路
帖　子：34
专家分：0
注　册：2008-6-4

问题点数：0 回复次数：2

求达人详细解释Hirschberg's Algorithm（LCS问题）（以解决）

如题，请帮我解释一下Hirschberg's Algorithm的实现过程。

谢谢！

[[it] 本帖最后由安静的小羊于 2008-10-7 09:52 编辑 [/it]]

搜索更多相关主题的帖子: LCS　Algorithm　Hirschberg　解释　

2008-10-05 14:04

很远的那颗星

等　级：新手上路
威　望：4
帖　子：544
专家分：0
注　册：2008-6-30

得分:0

LCS...DP呗..不过当两个序列达到上万个节点时，内存消耗就是个问题..空间复杂度为
O(m*n)
至于你说的Hirschberg's Algorithm...可以解决这个问题,空间复杂度只有O(m+n)..
具体过程请看书...或BAIDU或GOOGLE...

Fighting~~~~~~~~

2008-10-05 17:53

安静的小羊

来　自：广东
等　级：新手上路
帖　子：34
专家分：0
注　册：2008-6-4

得分:0

谢谢楼上，Hirschberg's Algorithm 我已经在他的论文中详细看了一遍，现在已经弄懂了！

我无所事事所度过的今天，是昨天死去的人们所奢望的明天 ...

2008-10-07 09:51