最长公共子序列和最长公共子串

  1. 云栖社区>
  2. 博客>
  3. 正文

最长公共子序列和最长公共子串

谙忆 2015-10-29 13:46:00 浏览542
展开阅读全文

什么是最长公共子序列呢?举个简单的例子吧,一个数列S,若分别是两个或多个已知序列的子序列,且是所有符合条件序列中最长的,则S称为已知序列的最长公共子序列。

举例如下,如:有两个随机数列,1 2 3 4 5 6 和 3 4 5 8 9,则它们的最长公共子序列便是:3 4 5。

之前一直不明白:最长公共子串和最长公共子序列的区别。

最长公共子串(Longest Common Substirng)和最长公共子序列(Longest Common Subsequence,LCS)的区别为:子串是串的一个连续的部分,子序列则是从不改变序列的顺序,而从序列中去掉任意的元素而获得新的序列;也就是说,子串中字符的位置必须是连续的,子序列则可以不必连续。
比如:s1: xyyxz
s2: xyyz
s1,s2的最大公共子序列为xyyz,最长公共子串为xyy;

网友评论

登录后评论
0/500
评论
谙忆
+ 关注