最长公共子序列和最长公共子串区别
最长公共子串(Longest Common Substring)与最长公共子序列(Longest Common Subsequence)的区别:
子串要求在原字符串中是连续的,而子序列则只需保持相对顺序一致,并不要求连续。
例如 X = {a, Q, 1, 1}; Y = {a, 1, 1, d, f}
那么,{1, 1}是X和Y的最长公共字串。
思路
我们的目的是寻找两个顺序绝对一致的序列
所以我们需要构建一个二维数组进行统计,记录遍历的时候他们相同的地方
设有这样的两个序列:
{A,A,C,G,T,T,A,G}
{A,C,G,T,A}
第一行的意思可以看作空和空.空和A。。。的最长子序列都为0
从第二行开始,如果相同就将左上角的值复制加一填入,所以这里就填上 1(0+1)
到C的时候,A和C是不一样的,直接填入0
到下一个A又相同,就把左上角的值加一填入
之后不一样的都填入0
到第二行时,C与C一样了,填入左上角的元素值加一,也就是1+1= 2,填入2
填完后得到
很明显表中的最大值就是他的最长子串
状态转移方程代码
通过以上的分解后,我们可以得到这样一个状态转移方程
if(a===b){ table[row][col] = table[row - 1][col - 1] + 1;//如果一样,我们找到他斜上角的那个值进行加一之后赋值
} else {
table[row][col] = 0; //如果不相同,我们就填入0
}
原文地址:http://www.cnblogs.com/kuailest/p/16879235.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性