最長(zhǎng)公共子串
題目：如果字符串一的所有字符按其在字符串中的順序出現(xiàn)在另外一個(gè)字符串二中，則字符串一稱之為字符串二的子串。注意，并不要求子串(字符串一)的字符必須連續(xù)出現(xiàn)在字符串二中。請(qǐng)編寫一個(gè)函數(shù)，輸入兩個(gè)字符串，求它們的最長(zhǎng)公共子串，并打印出最長(zhǎng)公共子串。
例如：輸入兩個(gè)字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它們的最長(zhǎng)公共子串，則輸出它們的長(zhǎng)度4，并打印任意一個(gè)子串。
分析：求最長(zhǎng)公共子串(Longest Common Subsequence, LCS)是一道非常經(jīng)典的動(dòng)態(tài)規(guī)劃題，因此一些重視算法的公司像MicroStrategy都把它當(dāng)作面試題。
完整介紹動(dòng)態(tài)規(guī)劃將需要很長(zhǎng)的篇幅，因此我不打算在此全面討論動(dòng)態(tài)規(guī)劃相關(guān)的概念，只集中對(duì)LCS直接相關(guān)內(nèi)容作討論。如果對(duì)動(dòng)態(tài)規(guī)劃不是很熟悉，請(qǐng)參考相關(guān)算法書比如算法討論。
先介紹LCS問(wèn)題的性質(zhì)：記Xm={x0, x1,…xm-1}和Yn={y0,y1,…,yn-1}為兩個(gè)字符串，而Zk={z0,z1,…zk-1}是它們的LCS，則：
1. 如果xm-1=yn-1，那么zk-1=xm-1=yn-1，并且Zk-1是Xm-1和Yn-1的LCS;
2. 如果xm-1≠yn-1，那么當(dāng)zk-1≠xm-1時(shí)Z是Xm-1和Y的LCS;
3. 如果xm-1≠yn-1，那么當(dāng)zk-1≠yn-1時(shí)Z是Yn-1和X的LCS;
下面簡(jiǎn)單證明一下這些性質(zhì)：
1. 如果zk-1≠xm-1，那么我們可以把xm-1(yn-1)加到Z中得到Z’，這樣就得到X和Y的一個(gè)長(zhǎng)度為k+1的公共子串Z’。這就與長(zhǎng)度為k的Z是X和Y的LCS相矛盾了。因此一定有zk-1=xm-1=yn-1。
既然zk-1=xm-1=yn-1，那如果我們刪除zk-1(xm-1、yn-1)得到的Zk-1，Xm-1和Yn-1，顯然Zk-1是Xm-1和Yn-1的一個(gè)公共子串，現(xiàn)在我們證明Zk-1是Xm-1和Yn-1的LCS。用反證法不難證明。假設(shè)有Xm-1和Yn-1有一個(gè)長(zhǎng)度超過(guò)k-1的公共子串W，那么我們把加到W中得到W’，那W’就是X和Y的公共子串，并且長(zhǎng)度超過(guò)k，這就和已知條件相矛盾了。
2. 還是用反證法證明。假設(shè)Z不是Xm-1和Y的LCS，則存在一個(gè)長(zhǎng)度超過(guò)k的W是Xm-1和Y的LCS，那W肯定也X和Y的公共子串，而已知條件中X和Y的公共子串的長(zhǎng)度為k。矛盾。
3. 證明同2。
有了上面的性質(zhì)，我們可以得出如下的思路：求兩字符串Xm={x0, x1,…xm-1}和Yn={y0,y1,…,yn-1}的LCS，如果xm-1=yn-1，那么只需求得Xm-1和Yn-1的LCS，并在其后添加xm-1(yn-1)即可;如果xm-1≠yn-1，我們分別求得Xm-1和Y的LCS和Yn-1和X的LCS，并且這兩個(gè)LCS中較長(zhǎng)的一個(gè)為X和Y的LCS。
如果我們記字符串Xi和Yj的LCS的長(zhǎng)度為c[i,j]，我們可以遞歸地求c[i,j]：
/ 0 if i<0 or j<0
c[i,j]= c[i-1,j-1]+1 if i,j>=0 and xi=xj
\ max(c[i,j-1],c[i-1,j] if i,j>=0 and xi≠xj
上面的公式用遞歸函數(shù)不難求得。但從前面求Fibonacci第n項(xiàng)(本面試題系列第16題)的分析中我們知道直接遞歸會(huì)有很多重復(fù)計(jì)算，我們用從底向上循環(huán)求解的思路效率更高。
為了能夠采用循環(huán)求解的思路，我們用一個(gè)矩陣(參考代碼中的LCS_length)保存下來(lái)當(dāng)前已經(jīng)計(jì)算好了的c[i,j]，當(dāng)后面的計(jì)算需要這些數(shù)據(jù)時(shí)就可以直接從矩陣讀取。另外，求取c[i,j]可以從c[i-1,j-1] 、c[i,j-1]或者c[i-1,j]三個(gè)方向計(jì)算得到，相當(dāng)于在矩陣LCS_length中是從c[i-1,j-1]，c[i,j-1]或者c[i-1,j]的某一個(gè)各自移動(dòng)到c[i,j]，因此在矩陣中有三種不同的移動(dòng)方向：向左、向上和向左上方，其中只有向左上方移動(dòng)時(shí)才表明找到LCS中的一個(gè)字符。于是我們需要用另外一個(gè)矩陣(參考代碼中的LCS_direction)保存移動(dòng)的方向。
參考代碼如下：
#include "string.h"
// directions of LCS generation
enum decreaseDir {kInit = 0, kLeft, kUp, kLeftUp};
/////////////////////////////////////////////////////////////////////////////
// Get the length of two strings' LCSs, and print one of the LCSs
// Input: pStr1 - the first string
// pStr2 - the second string
// Output: the length of two strings' LCSs
/////////////////////////////////////////////////////////////////////////////
int LCS(char* pStr1, char* pStr2)
{
if(!pStr1 || !pStr2)
return 0;
size_t length1 = strlen(pStr1);
size_t length2 = strlen(pStr2);
if(!length1 || !length2)
return 0;
size_t i, j;
// initiate the length matrix
int **LCS_length;
LCS_length = (int**)(new int[length1]);
for(i = 0; i < length1; ++ i)
LCS_length[i] = (int*)new int[length2];
for(i = 0; i < length1; ++ i)
for(j = 0; j < length2; ++ j)
LCS_length[i][j] = 0;
// 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 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。
題目：如果字符串一的所有字符按其在字符串中的順序出現(xiàn)在另外一個(gè)字符串二中，則字符串一稱之為字符串二的子串。注意，并不要求子串(字符串一)的字符必須連續(xù)出現(xiàn)在字符串二中。請(qǐng)編寫一個(gè)函數(shù)，輸入兩個(gè)字符串，求它們的最長(zhǎng)公共子串，并打印出最長(zhǎng)公共子串。
例如：輸入兩個(gè)字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它們的最長(zhǎng)公共子串，則輸出它們的長(zhǎng)度4，并打印任意一個(gè)子串。
分析：求最長(zhǎng)公共子串(Longest Common Subsequence, LCS)是一道非常經(jīng)典的動(dòng)態(tài)規(guī)劃題，因此一些重視算法的公司像MicroStrategy都把它當(dāng)作面試題。
完整介紹動(dòng)態(tài)規(guī)劃將需要很長(zhǎng)的篇幅，因此我不打算在此全面討論動(dòng)態(tài)規(guī)劃相關(guān)的概念，只集中對(duì)LCS直接相關(guān)內(nèi)容作討論。如果對(duì)動(dòng)態(tài)規(guī)劃不是很熟悉，請(qǐng)參考相關(guān)算法書比如算法討論。
先介紹LCS問(wèn)題的性質(zhì)：記Xm={x0, x1,…xm-1}和Yn={y0,y1,…,yn-1}為兩個(gè)字符串，而Zk={z0,z1,…zk-1}是它們的LCS，則：
1. 如果xm-1=yn-1，那么zk-1=xm-1=yn-1，并且Zk-1是Xm-1和Yn-1的LCS;
2. 如果xm-1≠yn-1，那么當(dāng)zk-1≠xm-1時(shí)Z是Xm-1和Y的LCS;
3. 如果xm-1≠yn-1，那么當(dāng)zk-1≠yn-1時(shí)Z是Yn-1和X的LCS;
下面簡(jiǎn)單證明一下這些性質(zhì)：
1. 如果zk-1≠xm-1，那么我們可以把xm-1(yn-1)加到Z中得到Z’，這樣就得到X和Y的一個(gè)長(zhǎng)度為k+1的公共子串Z’。這就與長(zhǎng)度為k的Z是X和Y的LCS相矛盾了。因此一定有zk-1=xm-1=yn-1。
既然zk-1=xm-1=yn-1，那如果我們刪除zk-1(xm-1、yn-1)得到的Zk-1，Xm-1和Yn-1，顯然Zk-1是Xm-1和Yn-1的一個(gè)公共子串，現(xiàn)在我們證明Zk-1是Xm-1和Yn-1的LCS。用反證法不難證明。假設(shè)有Xm-1和Yn-1有一個(gè)長(zhǎng)度超過(guò)k-1的公共子串W，那么我們把加到W中得到W’，那W’就是X和Y的公共子串，并且長(zhǎng)度超過(guò)k，這就和已知條件相矛盾了。
2. 還是用反證法證明。假設(shè)Z不是Xm-1和Y的LCS，則存在一個(gè)長(zhǎng)度超過(guò)k的W是Xm-1和Y的LCS，那W肯定也X和Y的公共子串，而已知條件中X和Y的公共子串的長(zhǎng)度為k。矛盾。
3. 證明同2。
有了上面的性質(zhì)，我們可以得出如下的思路：求兩字符串Xm={x0, x1,…xm-1}和Yn={y0,y1,…,yn-1}的LCS，如果xm-1=yn-1，那么只需求得Xm-1和Yn-1的LCS，并在其后添加xm-1(yn-1)即可;如果xm-1≠yn-1，我們分別求得Xm-1和Y的LCS和Yn-1和X的LCS，并且這兩個(gè)LCS中較長(zhǎng)的一個(gè)為X和Y的LCS。
如果我們記字符串Xi和Yj的LCS的長(zhǎng)度為c[i,j]，我們可以遞歸地求c[i,j]：
/ 0 if i<0 or j<0
c[i,j]= c[i-1,j-1]+1 if i,j>=0 and xi=xj
\ max(c[i,j-1],c[i-1,j] if i,j>=0 and xi≠xj
上面的公式用遞歸函數(shù)不難求得。但從前面求Fibonacci第n項(xiàng)(本面試題系列第16題)的分析中我們知道直接遞歸會(huì)有很多重復(fù)計(jì)算，我們用從底向上循環(huán)求解的思路效率更高。
為了能夠采用循環(huán)求解的思路，我們用一個(gè)矩陣(參考代碼中的LCS_length)保存下來(lái)當(dāng)前已經(jīng)計(jì)算好了的c[i,j]，當(dāng)后面的計(jì)算需要這些數(shù)據(jù)時(shí)就可以直接從矩陣讀取。另外，求取c[i,j]可以從c[i-1,j-1] 、c[i,j-1]或者c[i-1,j]三個(gè)方向計(jì)算得到，相當(dāng)于在矩陣LCS_length中是從c[i-1,j-1]，c[i,j-1]或者c[i-1,j]的某一個(gè)各自移動(dòng)到c[i,j]，因此在矩陣中有三種不同的移動(dòng)方向：向左、向上和向左上方，其中只有向左上方移動(dòng)時(shí)才表明找到LCS中的一個(gè)字符。于是我們需要用另外一個(gè)矩陣(參考代碼中的LCS_direction)保存移動(dòng)的方向。
參考代碼如下：
#include "string.h"
// directions of LCS generation
enum decreaseDir {kInit = 0, kLeft, kUp, kLeftUp};
/////////////////////////////////////////////////////////////////////////////
// Get the length of two strings' LCSs, and print one of the LCSs
// Input: pStr1 - the first string
// pStr2 - the second string
// Output: the length of two strings' LCSs
/////////////////////////////////////////////////////////////////////////////
int LCS(char* pStr1, char* pStr2)
{
if(!pStr1 || !pStr2)
return 0;
size_t length1 = strlen(pStr1);
size_t length2 = strlen(pStr2);
if(!length1 || !length2)
return 0;
size_t i, j;
// initiate the length matrix
int **LCS_length;
LCS_length = (int**)(new int[length1]);
for(i = 0; i < length1; ++ i)
LCS_length[i] = (int*)new int[length2];
for(i = 0; i < length1; ++ i)
for(j = 0; j < length2; ++ j)
LCS_length[i][j] = 0;
// 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 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。