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

如果我们记字符串X_i和Y_j的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 x_i=x_j
         \       max(c[i,j-1],c[i-1,j]           if i,j>=0 and x_i≠x_j

上面的公式用递归函数不难求得。但从前面求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下一页

    查看更多相关的文章

    欢迎分享转载→ 程序员面试题精选100题（20）－最长公共子串[算法](2)

    上一篇：程序员面试题精选100题（19）－反转链表

    下一篇：程序员面试题精选100题（21）－左旋转字符串[算法]

    相关文章

    用户评论