随笔 - 85  文章 - 47  trackbacks - 0

常用链接

随笔分类

随笔档案

搜索

  •  

最新评论

前段时间研究过如何求最长连续公共子序列和最长连续子字符串,以前一个同学正好问起来,这里贴出来解法:
问题的关键还是如何定义子问题,假设有:
Xm = x1 x2 x3 ... xm
Yn = y1 y2 y3 ... yn

1. 最长公共子序列(不必连续)
定义f(m, n)为Xm和Yn之间最长的子序列的长度
于是有f(m, 0) = f(0, m) = 0
如果xm != yn, 则f(m, n) = max{ f(m-1, n), f(m, n-1) }
如果xm = yn,则f(m, n) = f(m-1, n-1) + 1
问题归结于求f(m, n)。依照公式用Bottom-up DP可解。

2. 最长连续子字符串(必须是连续的)
定义f(m, n)为Xm和Yn之间最长的子字符串的长度并且该子字符串结束于Xm & Yn。因为要求是连续的,所以定义f的时候多了一个要求字符串结束于Xm & Yn
于是有f(m, 0) = f(0, m) = 0
如果xm != yn, 则f(m, n) = 0
如果xm = yn, 则f(m, n) = f(m-1, n-1) + 1
因为最长字符串不一定结束于Xm / Yn末尾,所以这里必须求得所有可能的f(p, q) | 0 < p < m, 0 < q < n, 最大的f(p, q)就是解。依照公式用Bottom-up DP可解。

转载自:http://blog.csdn.net/atfield/archive/2007/01/28/1496132.aspx

我的补充:最长连续子字符串问题与最大子段和问题有点类似。

posted on 2007-03-24 03:55 w2001 阅读(1721) 评论(0)  编辑 收藏 引用 所属分类: 算法设计

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理