// 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 LCS_Print(int **LCS_direction,

　　char* pStr1, char* pStr2,

　　size_t row, size_t col)

　　{

　　if(pStr1 == NULL || pStr2 == NULL)

　　return;

　　size_t length1 = strlen(pStr1);

　　size_t length2 = strlen(pStr2);

　　if(length1 == 0 || length2 == 0 || !(row < length1 && col < length2))

　　return;

　　// kLeftUp implies a char in the LCS is found

　　if(LCS_direction[row][col] == kLeftUp)

　　{

　　if(row > 0 && col > 0)

　　LCS_Print(LCS_direction, pStr1, pStr2, row - 1, col - 1);

　　// print the char

　　printf("%c", pStr1[row]);

　　}

　　else if(LCS_direction[row][col] == kLeft)

　　{

　　// move to the left entry in the direction matrix

　　if(col > 0)

　　LCS_Print(LCS_direction, pStr1, pStr2, row, col - 1);

　　}

　　else if(LCS_direction[row][col] == kUp)

　　{

　　// move to the up entry in the direction matrix

　　if(row > 0)

　　LCS_Print(LCS_direction, pStr1, pStr2, row - 1, col);

　　}

　　}

　　扩展：如果题目改成求两个字符串的最长公共子字符串，应该怎么求?子字符串的定义和子串的定义类似，但要求是连续分布在其他字符串中。比如输入两个字符串BDCABA和ABCBDAB的最长公共字符串有BD和AB，它们的长度都是2。

　　相关推荐：

　　2015年软考信息技术处理员考前知识点总结汇总

　　2015年软件水平考试《程序员》提高练习题汇总

　　2015软件水平考试《程序员》知识点总结汇总