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

本文是《算法图解》笔记

应用场景

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

  • 生物学家根据最长公共序列来确定 DNA 链的相似性,进而判断两种动物或疾病有多相似。最长公共序列还被用来寻找多发性硬化症治疗方案。
  • 源代码管理中,git diff指令,可以查找出编辑前后文件的差异,这是基于动态规划实现的。
  • 编辑距离(levenshtein distance),判断字符串的相似程度,也是基于动态规划计算。可以通过这个技术从拼写检查到判断用户上传的资料是否是盗版。(这样看来,我猜想大学论文查重应该也是基于动态规划算法:P
  • Microsoft Word等软件中具有断字功能,使用动态规划可以确定什么地方断字以确保行长一致。

最长公共子串

场景:

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

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

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

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

求解网格:
注:只列出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
算法描述:
  1. 如果两个字母不同,值为0
  2. 如果两个字母相同,值为左上角邻居的值加一
伪代码:
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
算法描述:
  1. 如果两个字母不同,就选择上方和左方邻居格子中较大的那个值
  2. 如果两个字母相同,值为左上方格子中的值加一
伪代码:
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])

交流

☕️赞助一杯咖啡☕️

取消

感谢支持,一起进步!

扫码支持
你的支持是对我的认可

打开 支付宝 扫一扫

Scroll to top