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

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

时间：2019-09-22 编辑：多美文
  •  
  • // initiate the direction matrix
  • int **LCS_direction;
  • LCS_direction = (int**)(new int[length1]);
  • for( i = 0; i < length1; ++ i)
  • LCS_direction[i] = (int*)new int[length2];
  •  
  • for(i = 0; i < length1; ++ i)
  • for(j = 0; j < length2; ++ j)
  • LCS_direction[i][j] = kInit;
  •  
  • for(i = 0; i < length1; ++ i)
  • {
  • for(j = 0; j < length2; ++ j)
  • {
  • if(i == 0 || j == 0)
  • {
  • if(pStr1[i] == pStr2[j])
  • {
  • LCS_length[i][j] = 1;
  • LCS_direction[i][j] = kLeftUp;
  • }
  • else
  • LCS_length[i][j] = 0;
  • }
  • // a char of LCS is found,
  • // it comes from the left up entry in the direction matrix
  • else if(pStr1[i] == pStr2[j])
  • {
  • LCS_length[i][j] = LCS_length[i - 1][j - 1] + 1;
  • LCS_direction[i][j] = kLeftUp;
  • }
  • // it comes from the up entry in the direction matrix
  • else if(LCS_length[i - 1][j] > LCS_length[i][j - 1])
  • {
  • LCS_length[i][j] = LCS_length[i - 1][j];
  • LCS_direction[i][j] = kUp;
  • }
  • // it comes from the left entry in the direction matrix
  • else
  • {
  • LCS_length[i][j] = LCS_length[i][j - 1];
  • LCS_direction[i][j] = kLeft;
  • }
  • }
  • }
  • LCS_Print(LCS_direction, pStr1, pStr2, length1 - 1, length2 - 1);
  •  
  • return LCS_length[length1 - 1][length2 - 1];
  • }
  •  
  •  
  •  
  • /////////////////////////////////////////////////////////////////////////////
  • // Print a LCS for two strings
  • // Input: LCS_direction - a 2d matrix which records the direction of
  • // LCS generation
  • // pStr1 - the first string
  • // pStr2 - the second string
  • // row - the row index in the matrix LCS_direction
  • // col - the column index in the matrix LCS_direction
  • /////////////////////////////////////////////////////////////////////////////
  • void
    共4页上一页1234下一页
    本文已影响 人
    相关文章
    好书推荐
    最新文章
    推荐文章
    推荐栏目

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

    多美文