最長公共子串問題的實現

　　最長公共子串問題：一個給定序列的子序列是在該序列中刪去若干元素后得到的序列。給定兩個序列X和Y，當另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列。最長公共子串就是求給定兩個序列的一個最長公共子序列。例如，X=“ABCBDAB”，Y=“BCDB”是X的一個子序列。

　　問題分析：

　　給定兩個序列A和B，稱序列Z是A和B的公共子序列，是指Z同是A和B的子序列。問題要求已知兩序列A和B的最長公共子序列。如采用列舉A的所有子序列，并一一檢查其是否又是B的子序列，并隨時記錄所發現的子序列，最終求出最長公共子序列。這種方法因耗時太多而不可取。

　　考慮最長公共子序列問題如何分解成子問題，設A=“a0，a1，…，am-1”，B=“b0，b1，…，bm-1”，并Z=“z0，z1，…，zk-1”為它們的最長公共子序列。不難證明有以下性質：

　　(1) 如果am-1=bn-1，則zk-1=am-1=bn-1，且“z0，z1，…，zk-2”是“a0，a1，…，am-2”和“b0，b1，…，bn-2”的一個最長公共子序列;

　　(2) 如果am-1!=bn-1，則若zk-1!=am-1，蘊涵“z0，z1，…，zk-1”是“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一個最長公共子序列;

　　(3) 如果am-1!=bn-1，則若zk-1!=bn-1，蘊涵“z0，z1，…，zk-1”是“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一個最長公共子序列。

　　這樣，在找A和B的公共子序列時，如有am-1=bn-1，則進一步解決一個子問題，找“a0，a1，…，am-2”和“b0，b1，…，bm-2”的一個 最長公共子序列;如果am-1!=bn-1，則要解決兩個子問題，找出“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一個最長公共子序列 和找出“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一個最長公共子序列，再取兩者中較長者作為A和B的最長公共子序列。

　　為了節約重復求相同子問題的時間，引入一個數組，不管它們是否對最終解有用，把所有子問題的解存于該數組中，這就是動態規劃法所采用的基本方法，具體說明如下。

　　定義c[i][j]為序列“a0，a1，…，ai-2”和“b0，b1，…，bj-1”的最長公共子序列的長度，計算c[i][j]可遞歸地表述如下：

　　(1)c[i][j] = 0 如果i=0或j=0;

　　(2)c[i][j] = c[i-1][j-1]+1 如果i,j>0，且a[i-1] = b[j-1];

　　(3)c[i][j] = max{c[i][j-1], c[i-1][j]} 如果i,j>0，且a[i-1] != b[j-1]。

　　按此算式可寫出計算兩個序列的最長公共子序列的長度函數。由于c[i][j]的產生僅依賴于c[i-1][j-1]、c[i-1][j]和c[i][j-1]，故可以從c[m][n]開始，跟蹤c[i][j]的產生過程，逆向構造出最長公共子序列。細節見程序。

　　#include

　　2011計算機等級考試二級C輔導實例編程匯總

　　計算機等級考試二級C語言歷年真題匯總(2005-2010)

　　2011年計算機等級考試二級C語言常見問題匯總

　　計算機等級考試二級C語言常見知識點總結