查看匯總：2015軟件水平考試程序員精選題匯總

　　最長公共子串

　　題目：如果字符串一的所有字符按其在字符串中的順序出現在另外一個字符串二中，則字符串一稱之為字符串二的子串。注意，并不要求子串(字符串一)的字符必須連續出現在字符串二中。請編寫一個函數，輸入兩個字符串，求它們的最長公共子串，并打印出最長公共子串。

　　例如：輸入兩個字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它們的最長公共子串，則輸出它們的長度4，并打印任意一個子串。

　　分析：求最長公共子串(Longest Common Subsequence, LCS)是一道非常經典的動態規劃題，因此一些重視算法的公司像MicroStrategy都把它當作面試題。

　　完整介紹動態規劃將需要很長的篇幅，因此我不打算在此全面討論動態規劃相關的概念，只集中對LCS直接相關內容作討論。如果對動態規劃不是很熟悉，請參考相關算法書比如算法討論。

　　先介紹LCS問題的性質：記Xm={x0, x1,…xm-1}和Yn={y0,y1,…,yn-1}為兩個字符串，而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，那么當zk-1≠xm-1時Z是Xm-1和Y的LCS;

　　3. 如果xm-1≠yn-1，那么當zk-1≠yn-1時Z是Yn-1和X的LCS;

　　下面簡單證明一下這些性質：

　　1. 如果zk-1≠xm-1，那么我們可以把xm-1(yn-1)加到Z中得到Z’，這樣就得到X和Y的一個長度為k+1的公共子串Z’。這就與長度為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的一個公共子串，現在我們證明Zk-1是Xm-1和Yn-1的LCS。用反證法不難證明。假設有Xm-1和Yn-1有一個長度超過k-1的公共子串W，那么我們把加到W中得到W’，那W’就是X和Y的公共子串，并且長度超過k，這就和已知條件相矛盾了。

　　2. 還是用反證法證明。假設Z不是Xm-1和Y的LCS，則存在一個長度超過k的W是Xm-1和Y的LCS，那W肯定也X和Y的公共子串，而已知條件中X和Y的公共子串的最大長度為k。矛盾。

　　3. 證明同2。

　　有了上面的性質，我們可以得出如下的思路：求兩字符串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，并且這兩個LCS中較長的一個為X和Y的LCS。

　　如果我們記字符串Xi和Yj的LCS的長度為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

　　上面的公式用遞歸函數不難求得。但從前面求Fibonacci第n項(本面試題系列第16題)的分析中我們知道直接遞歸會有很多重復計算，我們用從底向上循環求解的思路效率更高。

　　為了能夠采用循環求解的思路，我們用一個矩陣(參考代碼中的LCS_length)保存下來當前已經計算好了的c[i,j]，當后面的計算需要這些數據時就可以直接從矩陣讀取。另外，求取c[i,j]可以從c[i-1,j-1] 、c[i,j-1]或者c[i-1,j]三個方向計算得到，相當于在矩陣LCS_length中是從c[i-1,j-1]，c[i,j-1]或者c[i-1,j]的某一個各自移動到c[i,j]，因此在矩陣中有三種不同的移動方向：向左、向上和向左上方，其中只有向左上方移動時才表明找到LCS中的一個字符。于是我們需要用另外一個矩陣(參考代碼中的LCS_direction)保存移動的方向。

　　參考代碼如下：

　　#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;

　　}

　　相關推薦：

　　2015年軟考信息技術處理員考前知識點總結匯總

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

　　2015軟件水平考試《程序員》知識點總結匯總