// 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下一页

查看更多相关的文章

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

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

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

相关文章

用户评论