当前位置：多美文 > 求职面试 > 面试试题 > 程序员面试题精选100题（20）－最长公共子串[算法](2)

程序员面试题精选100题（20）－最长公共子串[算法](2)

时间：2019-09-22 编辑：多美文
，我们分别求得Xm-1和Y的LCS和Yn-1和X的LCS，并且这两个LCS中较长的一个为X和Y的LCS。

如果我们记字符串Xi和Yj的LCS的长度为c[i,j]，我们可以递归地求c[i,j]：

          /      0                               if i<0 or j<0
c[i,j]=          c[i-1,j-1]+1                    if i,j>=0 and xi=xj
         \       max(c[i,j-1],c[i-1,j]           if i,j>=0 and xi≠xj

上面的公式用递归函数不难求得。但从前面求Fibonacci第n项(本面试题系列第16题）的分析中我们知道直接递归会有很多重复计算，我们用从底向上循环求解的思路效率更高。

为了能够采用循环求解的思路，我们用一个矩阵（参考代码中的LCS_length）保存下来当前已经计算好了的c[i,j]，当后面的计算需要这些数据时就可以直接从矩阵读取。另外，求取c[i,j]可以从c[i-1,j-1]、c[i,j-1]或者c[i-1,j]三个方向计算得到，相当于在矩阵LCS_length中是从c[i-1,j-1]，c[i,j-1]或者c[i-1,j]的某一个各自移动到c[i,j]，因此在矩阵中有三种不同的移动方向：向左、向上和向左上方，其中只有向左上方移动时才表明找到LCS中的一个字符。于是我们需要用另外一个矩阵（参考代码中的LCS_direction）保存移动的方向。

参考代码如下：

 

  1. #include "string.h"
  2.  
  3. // directions of LCS generation
  4. enum decreaseDir {kInit = 0, kLeft, kUp, kLeftUp};
  5.  
  6. /////////////////////////////////////////////////////////////////////////////
  7. // Get the length of two strings' LCSs, and print one of the LCSs
  8. // Input: pStr1 - the first string
  9. // pStr2 - the second string
  10. // Output: the length of two strings' LCSs
  11. /////////////////////////////////////////////////////////////////////////////
  12. int LCS(char* pStr1, char* pStr2)
  13. {
  14. if(!pStr1 || !pStr2)
  15. return 0;
  16.  
  17. size_t length1 = strlen(pStr1);
  18. size_t length2 = strlen(pStr2);
  19. if(!length1 || !length2)
  20. return 0;
  21.  
  22. size_t i, j;
  23.  
  24. // initiate the length matrix
  25. int **LCS_length;
  26. LCS_length = (int**)(new int[length1]);
  27. for(i = 0; i < length1; ++ i)
  28. LCS_length[i] = (int*)new int[length2];
  29.  
  30. for(i = 0; i < length1; ++ i)
  31. for(j = 0; j < length2; ++ j)
  32. LCS_length[i][j] = 0;
  33.  
  34.  
    共4页上一页1234下一页
    本文已影响 人
    相关文章
    好书推荐
    最新文章
    推荐文章
    推荐栏目

关于我们|联系我们|常见问题|会员协议|法律声明|友情链接

多美文