// 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);

　　}

　　}

　　擴(kuò)展：如果題目改成求兩個(gè)字符串的最長(zhǎng)公共子字符串，應(yīng)該怎么求?子字符串的定義和子串的定義類似，但要求是連續(xù)分布在其他字符串中。比如輸入兩個(gè)字符串BDCABA和ABCBDAB的最長(zhǎng)公共字符串有BD和AB，它們的長(zhǎng)度都是2。

　　相關(guān)推薦：

　　2015年軟考信息技術(shù)處理員考前知識(shí)點(diǎn)總結(jié)匯總

　　2015年軟件水平考試《程序員》提高練習(xí)題匯總

　　2015軟件水平考試《程序員》知識(shí)點(diǎn)總結(jié)匯總