// 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页:
• 上一页
• 1
• 2
• 3
• 4
• 下一页

面试题推荐

面试题相关文章

• 秘书处面试问题及答案_学生会秘书处面试技巧
• 2022行政助理面试问题汇总
• 2022行政人员面试常见问题及回答技巧！
• 江苏公务员面试试题的参考答案
• 贵州公务员面试试题参考答案
• 历年吉林公务员面试试题答案
• 湖南公务员面试试题答案
• 黑龙江公务员面试试题答案
• 教师行业常见的面试问题
• 大学自主招生面试真题

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