美文网首页
最大公共子序列(LCS)

最大公共子序列(LCS)

作者: ticks | 来源:发表于2018-11-21 15:38 被阅读0次

子序列

子序列不要求字符连续(这与串不同)

公共子序列

两个字符串中的相同的子序列

  1. 最大公共子序列的例子
    字符串 X = sjdbfsb
    字符串 Y = sdfsdf
    LCS(X,Y) = sdf

算法

一些性质

字符串 x_{1,2,\cdots,i}, y_{1,2,\cdots, j} 最大公共子序列的长度

 LCS[i][j]

  1. 如果x_i=y_j, 即两个字符串的最后一个字符相同, 这个字符一定属于LCS.所以
if(x[i] == y[j])
LCS[i][j] = LCS[i - 1][j - 1] + 1
  1. 如果x_i != y_j, 则产生两个问题 LCS(x,y,i,j-1),LCS(x,y,i-1,j),因为要求最大的子序列长度,取两者中较大的一个
  2. 如果i或j等于0,结果是0

LCS[i][j]=\begin{cases}LCS[i-1][j-1]+1& x[i] = y[j]\\ \max\{LCS[i][j-1],LCS[i-1][j]\}&x[i]!=y[j]\\ 0&i==0||j==0\end{cases}

代码

int* LCS = new int[i * j];
for(int m = 0; m < j; m++)
{
  LCS[j] = 0;
}
for(int m = 0; m < i; m++)
{
  LCS[m * i] = 0;
} 
for(int m = 1; m < i; m++)
{
  for(int n = 1; n < j; n++)
  {
    if(x[i] == y[j]
      LCS[m * j + n] = LCS[(m - 1) * j + n-1] + 1;
    else
      LCS[m * j + n] = max(LCS[(m - 1) * j + n], LCS[m * j + n - 1]);
  }
}

动态规划从底向上, 每个子问题只解决一次, 如果需要解决过的结果只需要 "查表", 比普通递归需要更多的空间

相关文章

  • 子序列

    最长公共子序列(LCS)(lintcode 77) 描述:给出两个字符串,找到最长公共子序列(LCS),返回LCS...

  • lintcode 最长公共子序列

    给出两个字符串,找到最长公共子序列(LCS),返回LCS的长度。说明最长公共子序列的定义: 最长公共子序列问题是在...

  • 最大公共子序列(LCS)

    子序列 子序列不要求字符连续(这与串不同) 公共子序列 两个字符串中的相同的子序列 最大公共子序列的例子字符串 X...

  • LCS详解

    LCS是什么 LCS是Longest Common Subsequence的缩写,即最长公共子序列。一个序列,如果...

  • LCS解析,打印最大长度和路径

    LCS是什么 LCS是Longest Common Subsequence的缩写,即最长公共子序列。它与子串的区别...

  • LCS问题

    LCS问题包括最长公共子序列和最长公共子串,其中,最长公共子串要求必须连续。 对于二者的求解方式 最长公共子序列:...

  • 深度透析最长公共子序列算法

    最长公共子序列(Longest Common Subsequenen, LCS) 1、概念 动态规划(dynami...

  • 最长公共子序列问题

    最长公共子序列,英文缩写为LCS(Longest Common Subsequence)。其定义是,一个序列 S ...

  • (6)动态规划(上) LCS

    LCS 问题描述: 在两个给定的序列中, 找出最长的公共子序列(Largest Common Sequence),...

  • 最长递增子序列: 动态规划和LCS(最长公共子序列)

    最长递增子序列: 动态规划和LCS(最长公共子序列)子序列和子串的区别:子序列不连续,字串连续。这个题两种解法 动...

网友评论

      本文标题:最大公共子序列(LCS)

      本文链接:https://www.haomeiwen.com/subject/rshcqqtx.html