[算法笔记]动态规划之最长公共子串和最长公共子序列

DandJ 发布于2019-07-30 15:40 / 368人阅读

摘要：源代码管理中，指令，可以查找出编辑前后文件的差异，这是基于动态规划实现的。编辑距离，判断字符串的相似程度，也是基于动态规划计算。

本文是《算法图解》笔记

应用场景

一切脱离实际应用场景的算法都是耍流氓！

生物学家根据最长公共序列来确定 DNA 链的相似性，进而判断两种动物或疾病有多相似。最长公共序列还被用来寻找多发性硬化症治疗方案。

源代码管理中，git diff指令，可以查找出编辑前后文件的差异，这是基于动态规划实现的。

编辑距离（levenshtein distance），判断字符串的相似程度，也是基于动态规划计算。可以通过这个技术从拼写检查到判断用户上传的资料是否是盗版。（这样看来，我猜想大学论文查重应该也是基于动态规划算法:P）

Microsoft Word等软件中具有断字功能，使用动态规划可以确定什么地方断字以确保行长一致。

最长公共子串

场景：

某个用户在网站搜索框中输入一个字符串 hish，但其实用户想输入的是 fish

介绍这个网站的可选字典里面只有 fish 和 vista 这两个相似单词

猜测用户到底想要搜索的是什么字符串？

在动态规划中，目标是要将某个指标最大化，在这个例子中，要找出两个单词的公共子串。更大的那个即为结果。

求解网格：

注：只列出hish的例子，vista思路相同

	h	i	s	h
f	0	0	0	0
i	0	1	0	0
s	0	0	2	0
h	1	0	0	3

算法描述：

如果两个字母不同，值为0

如果两个字母相同，值为左上角邻居的值加一

伪代码：

if word_a[i] == word_b[j]:
    cell[i][j] = cell[i-1][j-1] + 1
else:
    cell[i][j] = 0

最长公共子序列

场景

假设用户不小心输入了 fosh ，要判断他原本要输入的是 fish 还是 fort

这时候需要使用最长公共子序列来比较

求解网络：

	f	o	s	h
f	1	1	1	1
i	1	1	1	1
s	1	1	2	2
h	1	1	2	3

算法描述:

如果两个字母不同，就选择上方和左方邻居格子中较大的那个值

如果两个字母相同，值为左上方格子中的值加一

伪代码：

if word_a[i] == word_b[j]:
    cell[i][j] = cell[i-1][j-1] + 1
else:
    cell[i][j] = max(cell[i-1][j], cell[i][j-1])

我的博客： http://vimiix.com

混合云云服务器最长公共子串最长公共子序列最大公共子串算法 java最长相同子串

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/41397.html

动态规划问题（2）——寻找最长公共子串

摘要：题目给定两个字符串求出它们的最长公共字串说明比如在单词和它们的最长公共子序列是。最长公共子串和最长公共子序列的区别。题目给定两个字符串,求出它们的最长公共字串 var str1=abcdefg; var str2=xyzabcd; 说明：比如在单词abcdefg和abcdefg它们的最长公共子序列是abcd。寻找最长子序列常用于遗传学中，用于使用核苷酸碱基的首字母对DNA的描述（这...

wushuiyong 2019-08-21 11:27 评论0 收藏0
算法设计 - LCS 最长公共子序列&&最长公共子串 &&LIS 最

摘要：若且，则是和的最长公共子序列若且，则是和的最长公共子序列。递归结构容易看到最长公共子序列问题具有子问题重叠性质。例如，在计算和的最长公共子序列时，可能要计算出和及和的最长公共子序列。虽是读书笔记，但是如转载请注明出处 http://segmentfault.com/blog/exploring/ .. 拒绝伸手复制党本章讲解： 1. LCS（最长公共子序列）O(n^2)的时间复杂...

weizx 2019-08-14 12:07 评论0 收藏0
字符串处理文章outline

摘要：遇到问题查查，看看，大神的讲解问问岛胖君下面是我最近整理出来的关于字符串的文章的怎么翻译汇集目录非常希望强化博客的功能，比如分类，置顶。虽是读书笔记，但是如转载请注明出处 http://segmentfault.com/blog/exploring/ .. 拒绝伸手复制党最近在看算法和语言，基本属于看知识 --> java实现 --> 整理blog 这个路线。遇到问题查查st...

Karuru 2019-08-14 15:07 评论0 收藏0
[算法总结] 搞定 BAT 面试——几道常见的子符串算法题

摘要：第一种方法常规方法。如果不存在公共前缀，返回空字符串。注意假设字符串的长度不会超过。说明本题中，我们将空字符串定义为有效的回文串。示例输入输出一个可能的最长回文子序列为。数值为或者字符串不是一个合法的数值则返回。说明本文作者：wwwxmu 原文地址:https://www.weiweiblog.cn/13s... 作者的博客站点：https://www.weiweiblog.c...

chanjarster 2019-08-19 11:07 评论0 收藏0
javascript 最长公共子序列

摘要：但不是和的最长公共子序列，而序列和也均为和的最长公共子序列，长度为，而和不存在长度大于等于的公共子序列。最长公共子序列给定序列和，从它们的所有公共子序列中选出长度最长的那一个或几个。为和的最长公共子序列长度。最长公共子序列（Longest Common Subsequence LCS）是从给定的两个序列X和Y中取出尽可能多的一部分字符，按照它们在原序列排列的先后次序排列得到。LCS问...

Xufc 2019-08-22 13:52 评论0 收藏0