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

線型動態(tài)規(guī)劃第1頁，課件共59頁，創(chuàng)作于2023年2月帶權有向的多段圖問題給定一個帶權的有向圖，要求從點A到點D的最短路徑。第2頁，課件共59頁，創(chuàng)作于2023年2月設F(i)表示從點A到達點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第3頁，課件共59頁，創(chuàng)作于2023年2月多階段最優(yōu)化決策問題由上例可以看出，整個問題分成了A、B、C、D四個階段來做，每個階段的數(shù)值的計算只會跟上一個階段的數(shù)值相關，這樣一直遞推下去直到目標。即由初始狀態(tài)開始，通過對中間階段決策的選擇，達到結(jié)束狀態(tài)。這些決策形成了一個決策序列，同時確定了完成整個過程的一條最優(yōu)的活動路線。第4頁，課件共59頁，創(chuàng)作于2023年2月狀態(tài)轉(zhuǎn)移方程設fk(i)—k階段狀態(tài)i的最優(yōu)權值，即初始狀態(tài)至狀態(tài)i的最優(yōu)代價。

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

第k+1階段狀態(tài)第k階段狀態(tài)決策第5頁，課件共59頁，創(chuàng)作于2023年2月動態(tài)規(guī)劃的基本原理最優(yōu)性原理

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

給定某一階段的狀態(tài)，則在這一階段以后過程的發(fā)展不受這階段以前各段狀態(tài)的影響，所有各階段都確定時，整個過程也就確定了。這個性質(zhì)意味著過程的歷史只能通過當前的狀態(tài)去影響它的未來的發(fā)展，這個性質(zhì)稱為無后效性。第6頁，課件共59頁，創(chuàng)作于2023年2月第1題：關鍵子工程有N個子工程，每一個子工程都有一個完成時間。子工程之間的有一些依賴關系，即某些子工程必須在一些子工程完成之后才開工。在滿足子工程間的依賴關系前提下，可以有任何多個子工程同時在施工。求整個工程的完成的最短時間。求出所有關鍵子工程。N≤200第7頁，課件共59頁，創(chuàng)作于2023年2月有向圖的關鍵路徑第8頁，課件共59頁，創(chuàng)作于2023年2月分析如果該圖能夠進行拓撲排序，證明有解，反之則無解。根據(jù)拓撲序列進行動態(tài)規(guī)劃求解，得到工程所需的完成時間。

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

動態(tài)規(guī)劃方程：F[I]=MAX{F[J]}+A[I，J]根據(jù)的得到的F序列和拓撲序列，查找關鍵工程。初始時，最后完成的一個或多個工程為關鍵工程。如果F[I]=F[J]-A[I，J]，且第I個子工程為關鍵工程，那么第J個子工程也是關鍵工程。時間復雜度為O(N2)。第9頁，課件共59頁，創(chuàng)作于2023年2月攔截導彈給定N個數(shù)求最長的不上升子序列長度求最少有多少個不上升序列能覆蓋所有的數(shù)，即求最少覆蓋序列。N<=10000.第10頁，課件共59頁，創(chuàng)作于2023年2月分析設f(i)表示前i個數(shù)的最長不上升序列的長度。

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

這里0<j<i<=n。

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

第11頁，課件共59頁，創(chuàng)作于2023年2月優(yōu)化分析樣例

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

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

該式子表示找前面的一個最大f的符合條件的j,因此只要保存符合條件的最大的j就可以了。在f值相同的情況下，保留較大的數(shù)顯然更好。因為后面的數(shù)若能跟較小的數(shù)構成下降序列也一定能能較大的數(shù)構成下降序列，反之則不一定。例如207與300的f=2,但207不能與299構成下降序列，而300則可以。因為生成的序列為有序序列，因此我們可以采用二分查找的方法很快查找到更新的值，時間復雜度為O(n㏒n)

第14頁，課件共59頁，創(chuàng)作于2023年2月求導彈的最小覆蓋第二問很容易想到貪心法：那就是采取多次求最長不上升序列的辦法，然后得出總次數(shù)。上述貪心法不正確，很容易就能舉出反例。

例如：“7541632”

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

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

但其實只要2套，分別為：

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

令（X,≤）是一個有限偏序集，并令m是反鏈的最大的大小。則X可以被劃分成m個但不能再少的鏈。雖然這兩個定理內(nèi)容相似，但第一個定理證明要簡單一些。此處就只證明定理1。第18頁，課件共59頁，創(chuàng)作于2023年2月證明：設p為最少反鏈個數(shù)(1)先證明X不能劃分成小于r個反鏈。由于r是最大鏈C的大小，C中任兩個元素都可比，因此C中任兩個元素都不能屬于同一反鏈。所以p>=r。(2)設X1＝X，A1是X1中的極小元的集合。從X1中刪除A1得到X2。注意到對于X2中任意元素a2，必存在X1中的元素a1，使得a1<=a2。令A2是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得證。第19頁，課件共59頁，創(chuàng)作于2023年2月解決要求最少的覆蓋，按照Dilworth定理最少鏈劃分=最長反鏈長度

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

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

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

AB+AB+A+CA+BA+AB

AB+A+BA+CA+BA+AB

長度為11第34頁，課件共59頁，創(chuàng)作于2023年2月分析為了盡快的查找到基元，我們把基元構成一個單詞樹，也叫trie樹。如下圖為樣例的單詞樹。該樹最多為26叉樹，任何單詞要么是某個單詞的前綴，要么為從根到葉子結(jié)點組成的單詞。這樣我們只需要O(L)的時間即可查找到某個單詞，L為單詞的長度。第35頁，課件共59頁，創(chuàng)作于2023年2月動態(tài)規(guī)劃我們設前j個字符已經(jīng)匹配，考慮前i個字符是否能匹配，主要看從i+1…j組成的字符串是否是單詞因此設f(i)表示前i個字符是否已匹配，若能匹配則為真(用1表示),否則為假(用0表示)。則有：第36頁，課件共59頁，創(chuàng)作于2023年2月時間復雜度分析每次求f(i)需要向前找f(j)，i-j<L,每移動一次j需要判定word(j+1,i)是否是單詞1<=i<=len(T),1<=i-j<L查找單詞時間復雜度為O(L)因此總時間復雜度為O(len(T)*L2)。因為T<=500000,L<=20,因此,5*105*202=2*108第37頁，課件共59頁，創(chuàng)作于2023年2月樣例實現(xiàn)過程，T:ABABACABAABCB，初始設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é)尾的單詞;第38頁，課件共59頁，創(chuàng)作于2023年2月優(yōu)化上述過程我們可以看出，每次求i，需要向前找j，這樣枚舉，再加上需要查找單詞，因此時間復雜度較高。如果要優(yōu)化，顯然字符串T必須至少掃描一遍，O(Len(T))不可能少。那么只能在查找單詞和枚舉j判斷字符串是否是單詞上做文章了。我們能否在查找單詞和枚舉字符串統(tǒng)一起來考慮呢?剛才解題思路是從后往前推，如果我們試著從前往后推會怎么樣呢？第39頁，課件共59頁，創(chuàng)作于2023年2月樣例實現(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并沒有回溯的過程，因此時間復雜度為O(len(T)*L)。T<=50000,L<=20,因此,5*105*20=107第40頁，課件共59頁，創(chuàng)作于2023年2月求最長公共子序列給定的字符序列X=“x0，x1，…，xm-1”，序列Y=“y0，y1，…，yk-1”是X的子序列，存在X的一個嚴格遞增下標序列<i0，i1，…，ik-1>，使得對所有的j=0，1，…，k-1，有xij=yj。例如，X=“ABCBDAB”，Y=“BCDB”是X的一個子序列。給出兩個字串S1和S2，長度不超過5000.求這兩個串的最長公共子串長度。第41頁，課件共59頁，創(chuàng)作于2023年2月分析樣例S1=“ABCBDAB.”S2=“BABCBD.”可以看出他們的最長公共子串有ABCB,ABCD,BCBD等，長度為4.從樣例分析，我們思考的方式為要找出S1串與S2串的公共子串，假設將S1固定，從第1個位置開始直到最后一個位置為止，與S2的各個部分不斷找最長公共子串當然S1也可以變化，這樣我們即得出了思路:枚舉S1的位置i枚舉S2的位置j找出S1的前i位與S2的前j位的最長公共子串，直到兩個串的最后一個位置為止。第42頁，課件共59頁，創(chuàng)作于2023年2月動態(tài)規(guī)劃設f(i,j)表示S的前i位與T的前j位的最長公共子串長度。則有，時間復雜度O(n*m)第43頁，課件共59頁，創(chuàng)作于2023年2月主程序框架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ù)組，實現(xiàn)f(i)與f(i-1)的滾動第44頁，課件共59頁，創(chuàng)作于2023年2月樣例運行過程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是因為最后都有一個”.”第45頁，課件共59頁，創(chuàng)作于2023年2月求連續(xù)的最長公共子串首先我們來分析一個簡單例子。LCS(‘212325233’,’

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

顯然該算法的時間復雜度為兩個串的長度乘積。第49頁，課件共59頁，創(chuàng)作于2023年2月求多個字符串的最長公共子串最長公共子串（Longestcommonsubstring,簡稱LCS）問題指的是求出給定的一組字符串的長度最大的共有的子字符串。

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

abcde

cdef

ccde

第50頁，課件共59頁，創(chuàng)作于2023年2月分析很容易想到枚舉算法，即枚舉某個串的子串，看是否是其他串的公共子串。顯然這個算法效率極低。長度為Ｌ的子串共Ｌ2個，然后,還要與其他N個子串分別求最長共子串，時間復雜度為長度的乘積。我們再來看看樣例：abcde

，cdef

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

樹上，如果找到深度最大

并且從屬于所有源字串的

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

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

點字符串拼接起來就是LCS。

第53頁，課件共59頁，創(chuàng)作于2023年2月最短回文串如果一個字符串正過來讀和倒過來讀是一樣的，那么這個字符串就被稱作回文串