線型動態(tài)規(guī)劃

線型動態(tài)規(guī)劃第一頁，共五十九頁，編輯于2023年，星期三帶權(quán)有向的多段圖問題給定一個帶權(quán)的有向圖，要求從點(diǎn)A到點(diǎn)D的最短路徑。第二頁，共五十九頁，編輯于2023年，星期三設(shè)F(i)表示從點(diǎn)A到達(dá)點(diǎn)i的最短距離，則有F(A)=0F(B1)=5,F(B2)=2F(C1)=min{F(B1)+3}=8F(C2)=min{F(B1)+2,F(B2)+7}=7F(C3)=min{F(B2)+4}=6F(D)=min{F(C1)+4,F(C2)+3,F(C3)+5}=10第三頁，共五十九頁，編輯于2023年，星期三多階段最優(yōu)化決策問題由上例可以看出，整個問題分成了A、B、C、D四個階段來做，每個階段的數(shù)值的計(jì)算只會跟上一個階段的數(shù)值相關(guān)，這樣一直遞推下去直到目標(biāo)。即由初始狀態(tài)開始，通過對中間階段決策的選擇，達(dá)到結(jié)束狀態(tài)。這些決策形成了一個決策序列，同時確定了完成整個過程的一條最優(yōu)的活動路線。第四頁，共五十九頁，編輯于2023年，星期三狀態(tài)轉(zhuǎn)移方程設(shè)fk(i)—k階段狀態(tài)i的最優(yōu)權(quán)值，即初始狀態(tài)至狀態(tài)i的最優(yōu)代價。

fk+1(i)=min{fk(j)+u(i,j)}

第k+1階段狀態(tài)第k階段狀態(tài)決策第五頁，共五十九頁，編輯于2023年，星期三動態(tài)規(guī)劃的基本原理最優(yōu)性原理

作為整個過程的最優(yōu)策略，它滿足：相對前面決策所形成的狀態(tài)而言，余下的子策略必然構(gòu)成“最優(yōu)子策略”。無后效性原則

給定某一階段的狀態(tài)，則在這一階段以后過程的發(fā)展不受這階段以前各段狀態(tài)的影響，所有各階段都確定時，整個過程也就確定了。這個性質(zhì)意味著過程的歷史只能通過當(dāng)前的狀態(tài)去影響它的未來的發(fā)展，這個性質(zhì)稱為無后效性。第六頁，共五十九頁，編輯于2023年，星期三第1題：關(guān)鍵子工程有N個子工程，每一個子工程都有一個完成時間。子工程之間的有一些依賴關(guān)系，即某些子工程必須在一些子工程完成之后才開工。在滿足子工程間的依賴關(guān)系前提下，可以有任何多個子工程同時在施工。求整個工程的完成的最短時間。求出所有關(guān)鍵子工程。N≤200第七頁，共五十九頁，編輯于2023年，星期三有向圖的關(guān)鍵路徑第八頁，共五十九頁，編輯于2023年，星期三分析如果該圖能夠進(jìn)行拓?fù)渑判?，證明有解，反之則無解。根據(jù)拓?fù)湫蛄羞M(jìn)行動態(tài)規(guī)劃求解，得到工程所需的完成時間。

設(shè)F[I]表示完成子工程I所需的最早時間。

動態(tài)規(guī)劃方程：F[I]=MAX{F[J]}+A[I，J]根據(jù)的得到的F序列和拓?fù)湫蛄?，查找關(guān)鍵工程。初始時，最后完成的一個或多個工程為關(guān)鍵工程。如果F[I]=F[J]-A[I，J]，且第I個子工程為關(guān)鍵工程，那么第J個子工程也是關(guān)鍵工程。時間復(fù)雜度為O(N2)。第九頁，共五十九頁，編輯于2023年，星期三攔截導(dǎo)彈給定N個數(shù)求最長的不上升子序列長度求最少有多少個不上升序列能覆蓋所有的數(shù)，即求最少覆蓋序列。N<=10000.第十頁，共五十九頁，編輯于2023年，星期三分析設(shè)f(i)表示前i個數(shù)的最長不上升序列的長度。

則, f(i)=max{f(j)+1},其中j<ianda[j]>=a[i]

這里0<j<i<=n。

顯然時間復(fù)雜度為O(n2)。上述式子的含義：找到i之前的某j，這個數(shù)不比第i個數(shù)小,對于所有的j取f(j)的最大值。

第十一頁，共五十九頁，編輯于2023年，星期三優(yōu)化分析樣例

這里找j,是在1~i之間進(jìn)行尋找，那么我們能否快速查找到我們所要更改的j呢?要能更改需要兩個條件：j<ianda[j]>=a[i]f(j)盡可能大

以上兩個條件提示我們后面的值一定要小于等于前面的值。因此我們試著構(gòu)建一個下降的序列。在這個下降的序列中查找可以更改的f值,使得序列的值盡可能大。i1234567838920715530029917015865f12323456第十二頁，共五十九頁，編輯于2023年，星期三具體過程：i1234567838920715530029917015865第1次389第2次389207第3次389207155第4次389300155（由于207<300<389,因此更新）第5次389300299（由于155<299<300,因此更新）第6次389300299170第7次389300299170158第8次38930029917015865第十三頁，共五十九頁，編輯于2023年，星期三思考？有些同學(xué)可能會問:對于每個f,為什么只保留一個數(shù)值呢?而對于該序列，為什么要保留較大的值呢？1. 再回過頭來看方程: f(i)=max{f(j)+1},其中j<ianda[j]>=a[i]

該式子表示找前面的一個最大f的符合條件的j,因此只要保存符合條件的最大的j就可以了。在f值相同的情況下，保留較大的數(shù)顯然更好。因?yàn)楹竺娴臄?shù)若能跟較小的數(shù)構(gòu)成下降序列也一定能能較大的數(shù)構(gòu)成下降序列，反之則不一定。例如207與300的f=2,但207不能與299構(gòu)成下降序列，而300則可以。因?yàn)樯傻男蛄袨橛行蛐蛄校虼宋覀兛梢圆捎枚植檎业姆椒ê芸觳檎业礁碌闹?，時間復(fù)雜度為O(n㏒n)

第十四頁，共五十九頁，編輯于2023年，星期三求導(dǎo)彈的最小覆蓋第二問很容易想到貪心法：那就是采取多次求最長不上升序列的辦法，然后得出總次數(shù)。上述貪心法不正確，很容易就能舉出反例。

例如：“7541632”

用多次求最長不上升序列所有為

“75432”、“1”、“6”共3套系統(tǒng)；

但其實(shí)只要2套，分別為：

“7541”與“632”。那么，正確的做法又是什么呢？第十五頁，共五十九頁，編輯于2023年，星期三分析上述問題的原因是若干次最優(yōu)決策值和不一定能推導(dǎo)出整個問題的最優(yōu)。為了解決這個問題下面介紹一個重要性質(zhì)：最少鏈劃分=最長反鏈長度為了證明這個性質(zhì)，需要了解離散數(shù)學(xué)中偏序集的相關(guān)概念和性質(zhì)以及偏序集的Dilworth定理。第十六頁，共五十九頁，編輯于2023年，星期三偏序集偏序是在集合X上的二元關(guān)系≤（這只是個抽象符號，不是“小于或等于”），它滿足自反性、反對稱性和傳遞性。即，對于X中的任意元素a,b和c，有:自反性：a≤a;反對稱性：如果a≤b且b≤a，則有a=b;傳遞性：如果a≤b且b≤c，則a≤c。帶有偏序關(guān)系的集合稱為偏序集。令(X,≤)是一個偏序集，對于集合中的兩個元素a、b，如果有a≤b或者b≤a，則稱a和b是可比的，否則a和b不可比。一個反鏈A是X的一個子集，它的任意兩個元素都不能進(jìn)行比較。一個鏈C是X的一個子集，它的任意兩個元素都可比。第十七頁，共五十九頁，編輯于2023年，星期三定理在X中，對于元素a，如果任意元素b，都有a≤b，則稱a為極小元。定理1：令（X,≤）是一個有限偏序集，并令r是其最大鏈的大小。則X可以被劃分成r個但不能再少的反鏈。其對偶定理稱為Dilworth定理：

令（X,≤）是一個有限偏序集，并令m是反鏈的最大的大小。則X可以被劃分成m個但不能再少的鏈。雖然這兩個定理內(nèi)容相似，但第一個定理證明要簡單一些。此處就只證明定理1。第十八頁，共五十九頁，編輯于2023年，星期三證明：設(shè)p為最少反鏈個數(shù)(1)先證明X不能劃分成小于r個反鏈。由于r是最大鏈C的大小，C中任兩個元素都可比，因此C中任兩個元素都不能屬于同一反鏈。所以p>=r。(2)設(shè)X1＝X，A1是X1中的極小元的集合。從X1中刪除A1得到X2。注意到對于X2中任意元素a2，必存在X1中的元素a1，使得a1<=a2。令A(yù)2是X2中極小元的集合，從X2中刪除A2得到X3……，最終會有一個Xk非空而Xk+1為空。于是A1,A2,…,Ak就是X的反鏈的劃分，同時存在鏈a1<=a2<=…<=ak，其中ai在Ai內(nèi)。由于r是最長鏈大小，因此r>=k。由于X被劃分成了k個反鏈，因此r>=k>=p。(3)因此r=p，定理1得證。第十九頁，共五十九頁，編輯于2023年，星期三解決要求最少的覆蓋，按照Dilworth定理最少鏈劃分=最長反鏈長度

所以最少多少套系統(tǒng)=最長導(dǎo)彈高度上升序列長度。知道了怎樣求最長不上升算法，同樣也就知道了怎樣求最長上升序列。時間復(fù)雜度O(n㏒n)。第二十頁，共五十九頁，編輯于2023年，星期三青蛙過河(NOIP2005)在河上有一座獨(dú)木橋，一只青蛙想沿著獨(dú)木橋從河的一側(cè)跳到另一側(cè)。在橋上有一些石子，青蛙很討厭踩在這些石子上。由于橋的長度和青蛙一次跳過的距離都是正整數(shù)，我們可以把獨(dú)木橋上青蛙可能到達(dá)的點(diǎn)看成數(shù)軸上的一串整點(diǎn)：0，1，……，L（其中L是橋的長度）。坐標(biāo)為0的點(diǎn)表示橋的起點(diǎn)，坐標(biāo)為L的點(diǎn)表示橋的終點(diǎn)。青蛙從橋的起點(diǎn)開始，不停的向終點(diǎn)方向跳躍。一次跳躍的距離是S到T之間的任意正整數(shù)（包括S,T）。當(dāng)青蛙跳到或跳過坐標(biāo)為L的點(diǎn)時，就算青蛙已經(jīng)跳出了獨(dú)木橋。題目給出獨(dú)木橋的長度L，青蛙跳躍的距離范圍S,T，橋上石子的位置。你的任務(wù)是確定青蛙要想過河，最少需要踩到的石子數(shù)。第二十一頁，共五十九頁，編輯于2023年，星期三【輸入文件】輸入文件river.in的第一行有一個正整數(shù)L（1<=L<=109），表示獨(dú)木橋的長度。第二行有三個正整數(shù)S，T，M，分別表示青蛙一次跳躍的最小距離，最大距離，及橋上石子的個數(shù)，其中1<=S<=T<=10，1<=M<=100。第三行有M個不同的正整數(shù)分別表示這M個石子在數(shù)軸上的位置（數(shù)據(jù)保證橋的起點(diǎn)和終點(diǎn)處沒有石子）。所有相鄰的整數(shù)之間用一個空格隔開。【輸出文件】輸出文件river.out只包括一個整數(shù)，表示青蛙過河最少需要踩到的石子數(shù)?！緲永斎搿?023523567【樣例輸出】2【數(shù)據(jù)規(guī)?！繉τ?0%的數(shù)據(jù)，L<=10000；對于全部的數(shù)據(jù)，L<=109。第二十二頁，共五十九頁，編輯于2023年，星期三分析由于不能往回跳，很容易想到用動態(tài)規(guī)劃解決這個題目。設(shè)f(i)表示跳到第i個點(diǎn)需要踩到的最少石子數(shù)，則很容易寫出動態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程:時間復(fù)雜度是O(L*(T-S))，但本題的L高達(dá)109，根本無法承受!

第二十三頁，共五十九頁，編輯于2023年，星期三進(jìn)一步分析我們先來考慮這樣一個問題：長度為k的一段沒有石子的獨(dú)木橋，判斷是否存在一種跳法從一端正好跳到另一端。若S<T，事實(shí)上對于某個可跳步長區(qū)間[S,T]，必然存在一個MaxK使得任何k>=MaxK，都可以從一端正好跳到另一端。題設(shè)中1<=S<=T<=10，經(jīng)過簡單推導(dǎo)或者程序驗(yàn)證就可以發(fā)現(xiàn)，取MaxK=100就能滿足所有區(qū)間。第二十四頁，共五十九頁，編輯于2023年，星期三

于是我們可以分兩種情況討論：1.S=T時： 這時候由于每一步只能按固定步長跳，所以若第i個位置上有石子并且imodS=0那么這個石子就一定要被踩到。這是我們只需要統(tǒng)計(jì)石子的位置中哪些是S的倍數(shù)即可。復(fù)雜度O(M)2.S<T時： 首先我們作如下處理：若存在某兩個相鄰石子之間的空白區(qū)域長度>MaxK+2*T，我們就將這段區(qū)域縮短成長度為MaxK+2*T?？梢宰C明處理之后的最優(yōu)值和原先的最優(yōu)值相同。 ab如上圖所示，白色點(diǎn)表示連續(xù)的一長段長度大于MaxK+2*T的空地，黑色點(diǎn)表示石子。設(shè)原先的最優(yōu)解中，白色段的第一個被跳到的位置a，最后一個被跳到的位置是b，則在做壓縮處理之后，a和b的距離仍然大于MaxK，由上面的結(jié)論可知，必存在一種跳法從a正好跳到b，而且不經(jīng)過任何石子。第二十五頁，共五十九頁，編輯于2023年，星期三所以原來的最優(yōu)解必然在處理之后的最優(yōu)解解集中。經(jīng)過這樣的壓縮處理，獨(dú)木橋的長度L’最多為(M+1)*(MaxK+2*T)+M，大約12000左右。壓縮之后再用先前的動態(tài)規(guī)劃求解，復(fù)雜度就簡化成了O(L’*(T-S))，已經(jīng)可以在時限內(nèi)出解了。這樣本題就得到了解決。第二十六頁，共五十九頁，編輯于2023年，星期三火車進(jìn)站給定N輛火車第i輛火車的進(jìn)站時間arrive(i)第i輛火車的離站時間leave(i)車站只能容納M輛火車求最多能接受多少輛火車？M<=3第二十七頁，共五十九頁，編輯于2023年，星期三先看樣第1，2，3輛分別進(jìn)入（123）；第2輛離開，可以看出要離開時，被第1輛火車卡在前面，因此第1輛火車不能進(jìn)入，隊(duì)列為（23）第2輛離開，第4輛進(jìn)入（34）第3，4輛離開，隊(duì)列空第5，6輛進(jìn)入（56）第5，6分別離開，隊(duì)列空因此答案為5輛第二十八頁，共五十九頁，編輯于2023年，星期三分析按到達(dá)時間排序和離開時間排序，這樣每一輛火車用線段描述，有：排在前面的火車，其進(jìn)站時間必須先于排在后面的火車；排在前面的火車，其出站時間必須先于排在后面的火車，否則該列火車就要先進(jìn)后出，不滿足隊(duì)列特點(diǎn)。這樣對于任一列排序后的火車i，只有排在其后的火車才有可能在它出站之后進(jìn)站。接下來的任務(wù)便是采用動態(tài)規(guī)劃方法求解了。第二十九頁，共五十九頁，編輯于2023年，星期三m=1時設(shè)f[i]表示第i列火車進(jìn)站時，其后的火車最多可以進(jìn)站的數(shù)量，則有：f[i]=max｛f[j]+1｝，（滿足i比j先進(jìn)站，且j在i出站之后進(jìn)站）；第三十頁，共五十九頁，編輯于2023年，星期三m=2設(shè)f[i,j]表示車站停靠i,j兩列火車(i<j)時，其后的火車（包括i,j本身）最多可以進(jìn)站的數(shù)量,則:f[i,j]=max｛f[j,k]+1｝條件：必須滿足按i,j,k順序進(jìn)站和出站，另外還要滿足k在i出站后且j進(jìn)站。第三十一頁，共五十九頁，編輯于2023年，星期三m=3設(shè)f[i,j,k]表示車站?？縤,j,k三列火車(i<j<k)時，其后的火車（包括i,j,k）最多可以進(jìn)站的數(shù)量。則有，f[i,j,k]=max{f[j,k,l]+1｝條件：必須滿足按i,j,k,l順序進(jìn)站和出站，另外還要滿足l在i出站后進(jìn)站。第三十二頁，共五十九頁，編輯于2023年，星期三最長前綴給定n個字符串，即基元給定一個字符串T，即生物體的結(jié)構(gòu)要找出字符串T由基元構(gòu)成的前綴，使得該前綴的長度最大N<=100,Len(T)<=500000,基元長度L<=20第三十三頁，共五十九頁，編輯于2023年，星期三樣例基元：A，AB，BBC，CA，BAT:ABABACABAABCB最長前綴構(gòu)成有三種方法A+BA+BA+CA+BA+AB

AB+AB+A+CA+BA+AB

AB+A+BA+CA+BA+AB

長度為11第三十四頁，共五十九頁，編輯于2023年，星期三分析為了盡快的查找到基元，我們把基元構(gòu)成一個單詞樹，也叫trie樹。如下圖為樣例的單詞樹。該樹最多為26叉樹，任何單詞要么是某個單詞的前綴，要么為從根到葉子結(jié)點(diǎn)組成的單詞。這樣我們只需要O(L)的時間即可查找到某個單詞，L為單詞的長度。第三十五頁，共五十九頁，編輯于2023年，星期三動態(tài)規(guī)劃我們設(shè)前j個字符已經(jīng)匹配，考慮前i個字符是否能匹配，主要看從i+1…j組成的字符串是否是單詞因此設(shè)f(i)表示前i個字符是否已匹配，若能匹配則為真(用1表示),否則為假(用0表示)。則有：第三十六頁，共五十九頁，編輯于2023年，星期三時間復(fù)雜度分析每次求f(i)需要向前找f(j)，i-j<L,每移動一次j需要判定word(j+1,i)是否是單詞1<=i<=len(T),1<=i-j<L查找單詞時間復(fù)雜度為O(L)因此總時間復(fù)雜度為O(len(T)*L2)。因?yàn)門<=500000,L<=20,因此,5*105*202=2*108第三十七頁，共五十九頁，編輯于2023年，星期三樣例實(shí)現(xiàn)過程，T:ABABACABAABCB，初始設(shè)f(0)=1f(1)=1,找到單詞A,且f(0)=1;f(2)=1,找到單詞AB,且f(0)=1;f(3)=1,找到單詞BA,且f(1)=1;f(4)=1,找到單詞AB,且f(2)=1;f(5)=1,找到單詞BA,且f(3)=1;f(6)=0,找不到以C結(jié)尾的單詞;f(7)=1,找到單詞CA,且f(5)=1;f(8)=0,盡管找到單詞AB，但f(6)=0;f(9)=1,找到單詞BA,且f(7)=1;f(10)=1,找到單詞A,且f(9)=1;f(11)=1,找到單詞AB,且f(9)=1;f(12)=0,找不到以C結(jié)尾的單詞;f(13)=0,找不到以B結(jié)尾的單詞;第三十八頁，共五十九頁，編輯于2023年，星期三優(yōu)化上述過程我們可以看出，每次求i，需要向前找j，這樣枚舉，再加上需要查找單詞，因此時間復(fù)雜度較高。如果要優(yōu)化，顯然字符串T必須至少掃描一遍，O(Len(T))不可能少。那么只能在查找單詞和枚舉j判斷字符串是否是單詞上做文章了。我們能否在查找單詞和枚舉字符串統(tǒng)一起來考慮呢?剛才解題思路是從后往前推，如果我們試著從前往后推會怎么樣呢？第三十九頁，共五十九頁，編輯于2023年，星期三樣例實(shí)現(xiàn)過程，T:ABABACABAABCB找到單詞A和AB,有f(1)=1,f(2)=1;找到單詞BA和AB,有f(3)=1,f(4)=1;找到單詞BA,有f(5)=1;找到單詞CA,有f(7)=1;找到單詞BA,有f(9)=1;找到單詞A和AB,有f(10)=1,f(11)=1;找不到以C開頭的單詞，程序結(jié)束。從上述過程我們可以看出，每次都是從前往后找單詞，只考慮f(i)=1開始后，是否有單詞，這樣我們對字符串T并沒有回溯的過程，因此時間復(fù)雜度為O(len(T)*L)。T<=50000,L<=20,因此,5*105*20=107第四十頁，共五十九頁，編輯于2023年，星期三求最長公共子序列給定的字符序列X=“x0，x1，…，xm-1”，序列Y=“y0，y1，…，yk-1”是X的子序列，存在X的一個嚴(yán)格遞增下標(biāo)序列<i0，i1，…，ik-1>，使得對所有的j=0，1，…，k-1，有xij=yj。例如，X=“ABCBDAB”，Y=“BCDB”是X的一個子序列。給出兩個字串S1和S2，長度不超過5000.求這兩個串的最長公共子串長度。第四十一頁，共五十九頁，編輯于2023年，星期三分析樣例S1=“ABCBDAB.”S2=“BABCBD.”可以看出他們的最長公共子串有ABCB,ABCD,BCBD等，長度為4.從樣例分析，我們思考的方式為要找出S1串與S2串的公共子串，假設(shè)將S1固定，從第1個位置開始直到最后一個位置為止，與S2的各個部分不斷找最長公共子串當(dāng)然S1也可以變化，這樣我們即得出了思路:枚舉S1的位置i枚舉S2的位置j找出S1的前i位與S2的前j位的最長公共子串，直到兩個串的最后一個位置為止。第四十二頁，共五十九頁，編輯于2023年，星期三動態(tài)規(guī)劃設(shè)f(i,j)表示S的前i位與T的前j位的最長公共子串長度。則有，時間復(fù)雜度O(n*m)第四十三頁，共五十九頁，編輯于2023年，星期三主程序框架n:=length(a);m:=length(b);fori:=1tonbeginforj:=1tomdobeginf[j]:=max(f[j-1],pf[j]);{從前面的狀態(tài)直接轉(zhuǎn)移過來}if(a[i]=b[j])and(pf[j-1]+1>f[j])then{多增加一位的情況}f[j]:=pf[j-1]+1;end;pf:=f;end;說明：pf是一個與f完全相同的數(shù)組，實(shí)現(xiàn)f(i)與f(i-1)的滾動第四十四頁，共五十九頁，編輯于2023年，星期三樣例運(yùn)行過程S=“ABCBDAB.”T=“BABCBD.”初始：f(i,0)=0,f(0,i)=0;∵S[1]≠T[1];∴f(1,1)=MAX{f(1,0),f(0,1)}=0∵S[1]=T[2];∴f(1,2)=MAX{f(1,0)+1}=1∵S[2]=T[1];∴f(2,1)=MAX{f(1,0)+1}=1∵S[2]≠T[2];∴f(2,2)=MAX{f(1,2),f(2,1)}=1∵S[2]=T[3];∴f(2,3)=MAX{f(1,2)+1}=2∵S[3]≠T[1];∴f(3,1)=MAX{f(3,0),f(2,1)}=1∵S[3]≠T[2];∴f(3,2)=MAX{f(2,2),f(3,1)}=1∵S[3]≠T[3];∴f(3,3)=MAX{f(3,2),f(2,3)}=2……一直求到f(8,7),ans=f(8,7)-1；減1是因?yàn)樽詈蠖加幸粋€”.”第四十五頁，共五十九頁，編輯于2023年，星期三求連續(xù)的最長公共子串首先我們來分析一個簡單例子。LCS(‘212325233’,’

312123223’)=‘21232’我們看是如何求解出來的,如下圖,紅色下劃線表示已匹配。第四十六頁，共五十九頁，編輯于2023年，星期三分析從前面例子可以看出解題思路：每次都是將子串的每一位與母串的每一位比較，然后根據(jù)比較的結(jié)果找LCS。因此，我們需要借助一個二維數(shù)組存儲兩個串比較后的結(jié)果，用１表示匹配成功，０表示不成功。如匹配結(jié)果如下圖(1),最長公共子串見圖(2)。第四十七頁，共五十九頁，編輯于2023年，星期三進(jìn)一步分析在0和1的矩陣中找最長的1對角線序列又要花去一定的時間。通過改進(jìn)矩陣的生成方式和設(shè)置標(biāo)記變量，可以省去這部分時間。下面是新的矩陣生成方式：第四十八頁，共五十九頁，編輯于2023年，星期三算法設(shè)置一個矩陣，記錄兩個串的匹配情況。當(dāng)字符匹配的時候，不是簡單的給相應(yīng)元素賦上1，而是賦上其左上角元素的值加１。我們用兩個標(biāo)記變量來標(biāo)記矩陣中值最大的元素的位置，在矩陣生成的過程中來判斷當(dāng)前生成的元素的值是不是最大的，據(jù)此來改變標(biāo)記變量的值，那么到矩陣完成的時候，最長匹配子串的位置和長度就已經(jīng)出來了。

顯然該算法的時間復(fù)雜度為兩個串的長度乘積。第四十九頁，共五十九頁，編輯于2023年，星期三求多個字符串的最長公共子串最長公共子串（Longestcommonsubstring,簡稱LCS）問題指的是求出給定的一組字符串的長度最大的共有的子字符串。

舉例以下三個字符串的LCS就是cde：

abcde

cdef

ccde

第五十頁，共五十九頁，編輯于2023年，星期三分析很容易想到枚舉算法，即枚舉某個串的子串，看是否是其他串的公共子串。顯然這個算法效率極低。長度為Ｌ的子串共Ｌ2個，然后,還要與其他N個子串分別求最長共子串，時間復(fù)雜度為長度的乘積。我們再來看看樣例：abcde

，cdef

，ccde回顧在求最長公共子串的過程中，子串往后移，實(shí)際上相對與母串往前移，然后將串的一部分與另一個串進(jìn)行比較。這實(shí)際上是利用了串的前綴或后綴。因此，我們試著構(gòu)造一棵后綴樹。第五十一頁，共五十九頁，編輯于2023年，星期三后綴樹后綴樹（GeneralizedSuffixTree，簡稱GST)算法，就是把給定的N個源字符串的所有的后綴建成一顆樹，這個樹有以下一些特點(diǎn)：樹的每個節(jié)點(diǎn)是一個字符串，樹根是空字符串“”任意一個后綴子串都可以由一條從根開始的路徑表達(dá)（將這條路徑上的結(jié)點(diǎn)字符串依次拼接起來就可以得到這個后綴）特別應(yīng)注意任意一個子串都可以看作某一個后綴的前綴。既然每一個后綴都可以由一條從根開始的路徑表達(dá)，那么我們可以從根節(jié)點(diǎn)開始一個字符一個字符的跟蹤這條路徑從而得到任意一個子串。為了滿足查找公共子串的需求，每個節(jié)點(diǎn)還應(yīng)該有從屬于哪個源字符串的信息。第五十二頁，共五十九頁，編輯于2023年，星期三前面我們學(xué)了trie樹，可以將后綴構(gòu)造一棵trie樹，如下圖。１：abcde，bcde，cde，de，e２：cdef，def，ef，f３：ccde，cde，de，e圖中標(biāo)識的數(shù)字表示該后綴屬于哪個串。我們不難看出，在這棵GST

樹上，如果找到深度最大

并且從屬于所有源字串的

節(jié)點(diǎn)，那么，把從根到這

個節(jié)點(diǎn)的路徑上的所有節(jié)

點(diǎn)字符串拼接起來就是LCS。

第五十三頁，共五十九頁，編輯于2023年，星期三最短回文串如果一個字符串正過來讀和倒過來讀是一樣的，那么這個字符串就被稱作回文串。