已填格子
匹配对
目前最长

  • 正在填写
  • 被读取
  • 答案

更多关于最长公共子序列

最长公共子序列(LCS)

两个单词有哪些字母是共有的,而且顺序相同?最长公共子序列回答的正是这个问题,diff 工具、拼写检查和 DNA 比对都建立在它之上。输入两个单词,观看由它们的字母组成的表格逐步填满,再从角落倒推出答案。 按“播放”观看表格填充过程,或用“单步”和“后退”一步一步查看。拖动步骤滑块可跳到任意位置。输入两个单词:第一个沿表格左侧从上往下排列,第二个沿顶部排列。每个格子存放的是到该行和该列为止的字母的最长公共子序列长度。最后,从右下角的格子开始倒推,读出这些字母。“新示例”会换一对单词。选中画板后,方向键单步前进或后退,空格键播放和暂停,Home 和 End 跳到开头和结尾。

它是如何运作的

  1. 输入两个单词:第一个沿表格左侧从上往下排列,第二个沿顶部排列。
  2. 按“播放”,或用“单步”和“后退”一步一步查看。拖动步骤滑块可跳到任意位置。
  3. 观看每个格子比较它的两个字母,然后沿橙色路径从角落往回走,读出答案。

表格的原理

每个格子存放的是第一个单词到该行为止的字母与第二个单词到该列为止的字母的最长公共子序列长度。标为 – 的行和列代表空单词,所以都是 0。如果格子对应的两个字母相同,该格子比左上方的格子多一。如果不同,两个字母中有一个不属于答案,所以格子取上方格子和左侧格子中较大的值。

倒推读出字母

右下角的格子就是答案的长度。要找出具体的字母,就从那里开始:在两个字母相同的地方,该字母属于子序列,然后向左上方移动;否则移向上方格子和左侧格子中较大的那个。把沿途收集到的字母倒过来读,就是一个最长公共子序列。可能还有其他同样长度的子序列;倒推只会找出其中一个。

常见问题

子序列和子串有什么区别?

子串是一段相邻的字母,比如 RACER 中的 ACE。子序列保持顺序,但可以跳过字母,所以 ACE 也是 ABCDE 的子序列。最长公共子串是另一个问题,所用的表格与此相似。

LCS 算法有多快?

对于长度为 m 和 n 的单词,表格有 m·n 个格子,每个格子一步填好,所以工作量是 O(m·n)。两个各有 1 万行的文本就有 1 亿个格子,所以 diff 工具使用基于同一思想的更巧妙的方法。

最长公共子序列是唯一的吗?

不是。ABCBDAB 和 BDCABA 有三个不同的长度为 4 的公共子序列:BCBA、BCAB 和 BDAB。表格给出长度;倒推从中选出一个。

LCS 能说明两个单词有多相似吗?

部分可以。长度为 m 和 n 的两个单词,如果最长公共子序列的长度为 k,就可以通过删除 m − k 个字母、插入 n − k 个字母相互转换。编辑距离还允许替换字母,通常是更好的衡量标准。

会把数据发送到别处吗?

不会。所有计算都在你的浏览器中完成,你最近的设置保存在此浏览器的本地存储中。

准备好尝试了吗?

在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。

前往编辑器