ACM集訓(xùn)隊(duì)階段總結(jié)課件

1、浙江林學(xué)院ACM集訓(xùn)隊(duì)階段總結(jié)Write by Zhuangli(zjfc3) 第1頁，共152頁。圖論What is that?第2頁，共152頁。什么是圖論?圖論Graph Theory是數(shù)學(xué)的一個(gè)分支。它以圖為研究對(duì)象。圖論中的圖是由若 干給定的點(diǎn)及連接兩點(diǎn)的線所構(gòu)成的圖形，這種圖形通常用來描述某些事物之間的某種特定關(guān)系，用點(diǎn)代表事物，用連接兩點(diǎn)的線表示相應(yīng)兩個(gè)事物間具有這種關(guān)系 。 圖論本身是應(yīng)用數(shù)學(xué)的一部份，因此，歷史上圖論曾經(jīng)被好多位數(shù)學(xué)家各自獨(dú)立地建立過。關(guān)于圖論的文字記載最早出現(xiàn)在歐拉1736年的論著中，他所考慮的原始問題有很強(qiáng)的實(shí)際背景。 第3頁，共152頁。并查集及其拓展并

2、查集是一種信息內(nèi)聚很強(qiáng)的數(shù)據(jù)結(jié)構(gòu)，它在判定圖的連通性以及等價(jià)類劃分的時(shí)空效率上有著不可替代的優(yōu)勢。但并查集的特殊應(yīng)用也應(yīng)該有所了解.以下兩類是并查集在實(shí)際問題中的特殊拓展，希望大家能夠進(jìn)行快速掌握.1.集合計(jì)數(shù)問題2.二分圖識(shí)別第4頁，共152頁。集合計(jì)數(shù)問題HDU 1856 More is better題意：若A與B認(rèn)識(shí)，B與C認(rèn)識(shí)，則A與C認(rèn)識(shí)，現(xiàn)給你一組人員的關(guān)系表，求在這樣的不同群組內(nèi)，擁有最多人數(shù)群組的人數(shù)。第5頁，共152頁。集合計(jì)數(shù)問題有什么想法？并查后統(tǒng)計(jì)并查數(shù)組?不可行 數(shù)據(jù)范圍10000000 如果逐個(gè)統(tǒng)計(jì)必定TLE 不能如此暴力.思路如何想3分鐘第6頁，共152頁。集合計(jì)

3、數(shù)問題聯(lián)想到并查集的構(gòu)造原理構(gòu)造rank數(shù)組,在并操作中入手！好,問題解決! 第7頁，共152頁。二分圖識(shí)別HDU 1829 A Bug Of Life題意：假定兩只飛蟲(Bug)關(guān)系表，如A B表示A仰慕B，問是否存在同性的飛蟲互相仰慕（也就是同性戀問題）.第8頁，共152頁。二分圖識(shí)別難點(diǎn)：A與B的集合歸屬不定如何解決?思考！第9頁，共152頁。二分圖識(shí)別非此即彼思想的運(yùn)用構(gòu)造數(shù)組opp，初始化為本身編號(hào)，若A與B有關(guān)，首先進(jìn)行find(A),find(B)的操作，若根相同，則說明A與B屬于同一集合，即同性戀，否則執(zhí)行下面的操作，如果A的opp等于本身，說明A的opp未初始化，使之等于B，

4、否則將A的opp與B進(jìn)行Unition操作，類似的如果B的opp等于本身，說明B的opp未初始化，使之等于A，否則將B的opp與A進(jìn)行Unition操作第10頁，共152頁。二分圖識(shí)別想想為什么？二分圖的性質(zhì)決定更深入的二分識(shí)別(如統(tǒng)計(jì)最小單元集，如何進(jìn)行 _ 課后思考!)第11頁，共152頁。最短路徑問題在一個(gè)網(wǎng)絡(luò)圖中求解一點(diǎn)到另一點(diǎn)間最短距離及其路徑的算法稱之為最短路徑問題。1、單源正權(quán)最短路徑2、單源帶負(fù)權(quán)最短路徑3、多源最短路徑第12頁，共152頁。單源正權(quán)最短路徑求解單源最短路徑的Dijkstra算法，狀態(tài)轉(zhuǎn)移與貪心準(zhǔn)則的完美結(jié)合。思想：動(dòng)態(tài)規(guī)劃 策略：貪心( O(Ve) )步驟：1

5、.構(gòu)造輔助數(shù)組Dis,Vist,Disi表示從源點(diǎn)出發(fā)到達(dá)i點(diǎn)的最短距離,Visti表示i點(diǎn)是否已被訪問，算法開始執(zhí)行時(shí)令所有Disi=w(start,i)不可達(dá)為MAX,Viststart=true.2.每次得到Dis數(shù)組中最小且未被訪問過的點(diǎn)i，標(biāo)記Visti=true,遍歷所有與i相關(guān)的邊，若得到Disi+w(i,j)Disj，則更新Disj=Disi+w(i ,j).3.如此循環(huán)直到所有點(diǎn)均被標(biāo)記.第13頁，共152頁。單源正權(quán)最短路徑Dijkstra的致命弱點(diǎn)：不能處理帶負(fù)權(quán)的邊思考：Why?問題出自貪心策略！若存在負(fù)權(quán)，則算法將不斷更新負(fù)權(quán)邊相關(guān)頂點(diǎn)的Dis值，從而導(dǎo)致答案錯(cuò)誤!第

6、14頁，共152頁。單源帶負(fù)權(quán)最短路徑如何處理Dijkstra的遺留問題？擯棄貪心策略 執(zhí)行松弛技術(shù)-Bellman-ford算法第15頁，共152頁。單源帶負(fù)權(quán)最短路徑什么是松弛技術(shù)？日常生活中的例子（1+1猜想）松弛技術(shù)的本質(zhì)是首先給予一個(gè)物體很高的估價(jià)，在每次的迭代中對(duì)估價(jià)進(jìn)行修正，在有限次的迭代后使估價(jià)與實(shí)際值吻合的技術(shù)。第16頁，共152頁。單源帶負(fù)權(quán)最短路徑思想：若存在N個(gè)點(diǎn)的網(wǎng)絡(luò)，則對(duì)于起點(diǎn)到終點(diǎn)最多經(jīng)過N-1條邊策略：有限迭代下的松弛技術(shù)第17頁，共152頁。單源帶負(fù)權(quán)最短路徑步驟：1、開辟輔助數(shù)組Dis,記錄源點(diǎn)到點(diǎn)i的最小距離，初始時(shí)設(shè)所有Dis值為MAX，Disstart

7、=0.2、進(jìn)行n-1次迭代，對(duì)于所有邊，若滿足DisiMAX&Disi+w(i,j)Disj,更新Disj= Disi+w(i,j).3、執(zhí)行完成后，再執(zhí)行1次迭代，若出現(xiàn)Disi+w(i,j)Disj的情況，則表明出現(xiàn)了負(fù)環(huán)，此時(shí)不存在最短路徑，否則Disend即所求單源最短路徑.第18頁，共152頁。單源帶負(fù)權(quán)最短路徑算法分析：1、迭代v-1次，每次遍歷所有邊,復(fù)雜度O（VE）,E為全部邊，Dijkstra的復(fù)雜度O(Ve),e為部分邊.效率差別很大!2、如何優(yōu)化？思考！第19頁，共152頁。單源帶負(fù)權(quán)最短路徑優(yōu)化1：使用bool值Y 標(biāo)記此次迭代是否進(jìn)行松弛，若沒進(jìn)行松弛表明已經(jīng)得到最短

8、路徑，因此跳出循環(huán)。（常系數(shù)優(yōu)化）-YEN氏優(yōu)化優(yōu)化2：使用標(biāo)記數(shù)組以及隊(duì)列輔助，初始化時(shí)推入start點(diǎn)，標(biāo)記start在隊(duì)內(nèi)，每次執(zhí)行時(shí)，將隊(duì)首推出，標(biāo)記其不在隊(duì)內(nèi)，遍歷其鄰邊，進(jìn)行松弛操作，將所有不在隊(duì)內(nèi)且進(jìn)行過松弛操作的邊相關(guān)的點(diǎn)入隊(duì)直到隊(duì)列為空（即不再進(jìn)行松弛操作）-SPFA！第20頁，共152頁。單源帶負(fù)權(quán)最短路徑由優(yōu)化2得到的正是傳說中的SPFA，擁有神一般的效率O（KE），K一般取值3-5。算法如其名Shortest Path Fast Algorithm!瓶頸：如何判負(fù)環(huán)？思考！當(dāng)一個(gè)點(diǎn)入隊(duì)次數(shù)超過邊的次數(shù)！需要輔助數(shù)組統(tǒng)計(jì)各點(diǎn)入隊(duì)次數(shù)，此時(shí)的空間與時(shí)間效率都極低！因此此算法

9、在稠密帶負(fù)環(huán)圖中的表現(xiàn)不如bellman-ford的YEN氏優(yōu)化！請大家慎重選擇使用。第21頁，共152頁。多源最短路徑當(dāng)題目要求大量的查詢工作時(shí)，需要一種算法能在多項(xiàng)式時(shí)間內(nèi)得到所有頂點(diǎn)間的最短距離并保存結(jié)果備查。Floyed算法應(yīng)運(yùn)而生!第22頁，共152頁。多源最短路徑思想：傳遞關(guān)系閉包策略：動(dòng)態(tài)規(guī)劃O (V*V*V)步驟：1、對(duì)于點(diǎn)k，若存在w(i,k)+w(k,j)=(或=)C（常數(shù)）,以此為模型構(gòu)成的約束系統(tǒng)，稱之為差分約束系統(tǒng)。第36頁，共152頁。差分約束初步首先我們回顧下松弛技術(shù)，在Bellman-Ford算法中，有一個(gè)十分關(guān)鍵的三角不等式Disi+w(i,j)Disj使得迭

10、代結(jié)束后所有的Disj=（或=）C，我們?nèi)?情況研究,則要求xi-xj=C，即xi=wi,j始終 成立。KM算法的正確性基于以下定理： 若由二分圖中所有滿足Ai+Bj=wi,j的邊(i,j)構(gòu)成的子圖（稱做相等子圖）有完備匹配，那么這個(gè)完備匹配就是二分圖的最大權(quán)匹配。這個(gè)定理是顯然的。因?yàn)閷?duì)于二分圖的任意一個(gè)匹配，如果它包含于相等子圖，那么它的邊權(quán)和等于所有頂點(diǎn)的頂標(biāo)和；如果它有的邊不包含于相等子圖，那么它的邊權(quán)和小于所有頂點(diǎn)的頂標(biāo)和。所以相等子圖的完備匹配一定是二分圖的最大權(quán)匹配。 算法的本質(zhì)是對(duì)匈牙利算法的改進(jìn)，但實(shí)際上卻比匈牙利算法早發(fā)表幾年，其核心仍然是尋找增廣路徑的過程。第42頁，共

11、152頁。KM算法步驟初始時(shí)為了使Ai+Bj=wi,j恒成立，令A(yù)i為所有與頂點(diǎn)Xi關(guān)聯(lián)的邊的最大權(quán)，Bj=0。如果當(dāng)前的相等子圖沒有完備匹配，就按下面的方法修改頂標(biāo)以使擴(kuò)大相等子圖，直到相等子圖具有完備匹配為止。 我們求當(dāng)前相等子圖的完備匹配失敗了，是因?yàn)閷?duì)于某個(gè)X頂點(diǎn)，我們找不到一條從它出發(fā)的交錯(cuò)路。這時(shí)我們獲得了一棵交錯(cuò)樹，它的葉子結(jié)點(diǎn)全部是X頂點(diǎn)?，F(xiàn)在我們把交錯(cuò)樹中X頂點(diǎn)的頂標(biāo)全都減小某個(gè)值d，Y頂點(diǎn)的頂標(biāo)全都增加同一個(gè)值d，那么我們會(huì)發(fā)現(xiàn)： 兩端都在交錯(cuò)樹中的邊(i,j)，Ai+Bj的值沒有變化。也就是說，它原來屬于相等子圖，現(xiàn)在仍屬于相等子圖。 兩端都不在交錯(cuò)樹中的邊(i,j)，A

12、i和Bj都沒有變化。也就是說，它原來屬于（或不屬于）相等子圖，現(xiàn)在仍屬于（或不屬于）相等子圖。 X端不在交錯(cuò)樹中，Y端在交錯(cuò)樹中的邊(i,j)，它的Ai+Bj的值有所增大。它原來不屬于相等子圖，現(xiàn)在仍不屬于相等子圖。 X端在交錯(cuò)樹中，Y端不在交錯(cuò)樹中的邊(i,j)，它的Ai+Bj的值有所減小。也就說，它原來不屬于相等子圖，現(xiàn)在可能進(jìn)入了相等子圖，因而使相等子圖得到了擴(kuò)大。 現(xiàn)在的問題就是求d值了。為了使Ai+Bj=wi,j始終成立，且至少有一條邊進(jìn)入相等子圖，d應(yīng)該等于minAi+Bj-wi,j|Xi在交錯(cuò)樹中，Yi不在交錯(cuò)樹中。 理解原理就行，在一般情況下KM算法的代碼不會(huì)調(diào)整，因此只要會(huì)使

13、用模版，一切不在話下，當(dāng)然圖論本身就是充滿了建模的思想，只有好的模型才能有真正的效率！第43頁，共152頁。KM算法效率 O（V*V*V）KM算法的本質(zhì)，對(duì)于N*N的矩陣每行每列只能取一個(gè)數(shù)，使其和為最大！第44頁，共152頁。強(qiáng)連通分支什么是強(qiáng)連通分支？強(qiáng)連通分支就是任意兩點(diǎn)均可達(dá)的有向子圖。理論：白色路徑定理求解：Tarjan算法第45頁，共152頁。強(qiáng)連通分支什么是時(shí)間戳？DFS進(jìn)行時(shí)，訪問到節(jié)點(diǎn)所花的時(shí)間算法理論依據(jù)：DFS時(shí)，如果所達(dá)的下一個(gè)點(diǎn)i已經(jīng)被訪問，則從該點(diǎn)j出發(fā)，尋找父節(jié)點(diǎn)到i，其間所經(jīng)過的所有點(diǎn)必為以i為代表的強(qiáng)連通分支上的點(diǎn)(并查實(shí)現(xiàn))如何判斷是否是該次被訪問？時(shí)間戳！

14、第46頁，共152頁。強(qiáng)連通分支步驟對(duì)于每個(gè)頂點(diǎn)，設(shè)立Num、Low、Used、Alive四個(gè)屬性，一個(gè)Stack保存當(dāng)前正在被遍歷的頂點(diǎn)；每訪問一個(gè)頂點(diǎn)，將它的Num和Low設(shè)立為當(dāng)前時(shí)間戳，Used、Alive設(shè)為True，并將頂點(diǎn)入棧；對(duì)于它的每條邊，若邊的終點(diǎn)未Used，則訪問，而后用終點(diǎn)的Low值更新它的Low值，對(duì)于每個(gè)Used且Alive的終點(diǎn)，用它的Num值更新當(dāng)前值；訪問完畢當(dāng)前頂點(diǎn)后，若Low與Num相等，說明找到了一個(gè)強(qiáng)連通分量，它包括棧中所有在當(dāng)前頂點(diǎn)上方的頂點(diǎn)，將它們出棧并記下Belong值，出棧的頂點(diǎn)的Alive要置為false。掃描各點(diǎn)Belong值，其代表的點(diǎn)的

15、個(gè)數(shù)便為強(qiáng)連通分支數(shù)！第47頁，共152頁。強(qiáng)連通分支應(yīng)用1、求解單純問題 HDU 12692、縮圖技術(shù) (適用于多點(diǎn)多邊的關(guān)系閉包求解)第48頁，共152頁。待研究的問題次小生成樹最優(yōu)比例生成樹最小樹型圖弦圖穩(wěn)定婚姻問題第49頁，共152頁。數(shù)論Its easy to learn!第50頁，共152頁。數(shù)論什么是數(shù)論？數(shù)論是研究整數(shù)性質(zhì)的一門很古老的數(shù)學(xué)分支， 其初等部分是以整數(shù)的整除性為中心的，包括整除性、不定方程、同余式、連分?jǐn)?shù)、素?cái)?shù)（即整數(shù)）分布 以及數(shù)論函數(shù)等內(nèi)容，統(tǒng)稱初等數(shù)論（elementary number theory）。 初等數(shù)論的大部份內(nèi)容早在古希臘歐幾里德的 幾何原本中

16、就已出現(xiàn)。歐幾里得證明了素?cái)?shù)有無窮多個(gè)，他還給出求兩個(gè)自然數(shù)的最大公約數(shù)的方法， 即所謂歐幾里得算法。我國古代在數(shù)論方面亦有杰出之貢獻(xiàn)，現(xiàn)在一般數(shù)論書中的中國剩余定理正是我國古代孫子算經(jīng)中的下卷第26題，我國稱之為 孫子定理。 近代初等數(shù)論的發(fā)展得益于費(fèi)馬、歐拉、拉格朗日、勒讓德和高斯等人的工作。1801年，高斯的算術(shù)探究是數(shù)論的劃時(shí)代杰作。高斯還提出：數(shù)學(xué)是科學(xué)的皇后，數(shù)論是數(shù)學(xué)中的皇冠?？梢姼咚箤?duì)數(shù)論的高度評(píng)價(jià)。 由于自20世紀(jì)以來引進(jìn)了抽象數(shù)學(xué)和高等分析的 巧妙工具，數(shù)論得到進(jìn)一步的發(fā)展，從而開闊了新的研究領(lǐng)域，出現(xiàn)了代數(shù)數(shù)論、解析數(shù)論、幾何數(shù)論等 新分支。而且近年來初等數(shù)論在計(jì)算器科學(xué)

17、、組合數(shù)學(xué)、密碼學(xué)、代數(shù)編碼、計(jì)算方法等領(lǐng)域內(nèi)更得到了廣泛的應(yīng)用，無疑同時(shí)間促進(jìn)著數(shù)論的發(fā)展。 第51頁，共152頁。同余定理對(duì)于正整數(shù)a,b,c(a%c+b%c)%c=(a+b)%c(a*b)%c=(a%c*b%c)%c注意對(duì)于除法與減法%運(yùn)算為非封閉運(yùn)算 需要進(jìn)行數(shù)論變換才能繼續(xù)進(jìn)行下去第52頁，共152頁。同余定理大數(shù)求余設(shè)大數(shù)R=a1*100+a2*101+.+an*10n-1則R%C=(a1*100%C+a2*101%C+.+an*10n-1%C)%C可以在O（logn）時(shí)間內(nèi)解決大數(shù)求余問題步驟：以字符讀入大數(shù)后，設(shè)置計(jì)數(shù)器sum=0 sum=(10*sum+keyi-0)%C;迭

18、代后令sum=sum%C;第53頁，共152頁。GCDGCD（最大公約數(shù)）的一般求解歐幾里德輾轉(zhuǎn)相除法（必須掌握）If(a%b=0) return b;Else return gcd(b,a%b);本過程具有收斂性質(zhì)第54頁，共152頁。擴(kuò)展歐幾里德在一些具體的題目中，我們還需要的到一組滿足ax+by=gcd(a,b)的最小解，用以判斷模方程是否有解，此時(shí)就要使用擴(kuò)展歐幾里德.相比一般歐幾里德方法，擴(kuò)展歐幾里德有一個(gè)對(duì)于X，Y求解的遞推過程。使用遞歸實(shí)現(xiàn)，遞歸條件為b=0時(shí)，X=1,Y=0;否則t=X; X=Y; Y=t-(a/b)*X;(遞推求得)可以證明最后出來的X，Y必然是最小解.應(yīng)用：

19、模線性方程的求解第55頁，共152頁。循環(huán)群生成元對(duì)于mod n域中的任意數(shù)a，若有g(shù)cd(m,n)=1，則m為該域的生成元，使得a+km可以為域中任意數(shù).證明十分簡單，若gcd(m,n)=1，則lcm(m,n)=m*n,則對(duì)于a的mod n運(yùn)算,需要n次的計(jì)算才能回到a，期間必遍歷該域中所有數(shù)！第56頁，共152頁。因子分解對(duì)于篩選大量數(shù)的因子分解工作，可以與篩選質(zhì)數(shù)同時(shí)進(jìn)行。令leni記錄數(shù)i的因子個(gè)數(shù)，則對(duì)于每個(gè)素?cái)?shù)p的倍數(shù)及本身，插入因子p，并使len值增長，篩選完所有素?cái)?shù)后就完成了因子分解第57頁，共152頁。素?cái)?shù)判定對(duì)于一千萬內(nèi)素?cái)?shù)的判定：篩選法最優(yōu)對(duì)于一千萬外素?cái)?shù)的判定：米勒測試

20、第58頁，共152頁。篩選法給定輔助bool數(shù)組prime，首先全置true,使prime0=prime1=false;遍歷，當(dāng)遇到primei=true,將之小于n的所有倍數(shù)置false；最后一次遍歷，所有值為true的數(shù)即為素?cái)?shù)！時(shí)空效率 均攤相關(guān)偽線性復(fù)雜度第59頁，共152頁。米勒測試?yán)碚摶A(chǔ)費(fèi)馬定理實(shí)踐工具二分求冪第60頁，共152頁。米勒測試費(fèi)馬定理：若p為素?cái)?shù)-a(p-1)%p=1注意此定理只為充分 不為必要米勒測試以概率的形式避免了誤判的發(fā)生 從嚴(yán)格意義上來說米勒測試的意義并不科學(xué) 但是實(shí)際證明在可數(shù)范圍內(nèi)的偽素?cái)?shù)十分之少 而且同時(shí)滿足a=2,a=3,a=7的底的偽素?cái)?shù)更是少得

21、可憐，因此該測試從概率上滿足了快速判定素?cái)?shù)的需求。第61頁，共152頁。米勒測試二分快速求冪模原理對(duì)于res=ab%c的求解若b%2=0則res=(a(b/2)%c*(a(b/2)%c)%c否則res=(a*(a(b/2)%c*(a(b/2)%c)%c第62頁，共152頁。歐拉函數(shù)設(shè)E(n)為n以內(nèi)（不包括n）與n互質(zhì)數(shù)的個(gè)數(shù)，則E(n)稱為關(guān)于n的歐拉函數(shù)。歐拉函數(shù)的求法，對(duì)于n=p1*p2*p3pnE(n)=n*(1-1/p1)*(1-1/p2)*(1-1/pn)可以以容斥原理證明其正確性！歐拉定理: a(E(n)%n=1第63頁，共152頁。模線性方程求解axb(mod n)有解，當(dāng)且僅

22、當(dāng)b%gcd(a,n)=0使用擴(kuò)展歐幾里德求得d=gcd(a,n),則aX+nY=d,x=(X*(b/d)%nWhy?b/d=m a(X*m)+nY*m=b=x=(X*m)%n第64頁，共152頁。中國剩余定理設(shè) n=n1*n2.nk, 其中因子兩兩互質(zhì).有: a-(a1,a2,.,ak), 其中ai = a mod ni, 則 a和(a1,a2,.,ak),關(guān)系是一一對(duì)應(yīng)的.就是說可以由 a求出(a1,a2,.,ak), 也可以由(a1,a2,.,ak)求出a求解：中國古代演算法模線性方程代入第65頁，共152頁。中國剩余定理應(yīng)用大整數(shù)表示快速運(yùn)算第66頁，共152頁。連分?jǐn)?shù)逼近在數(shù)學(xué)中，連

23、分?jǐn)?shù)或繁分?jǐn)?shù)即如上表達(dá)式.這里的 a0 是某個(gè)整數(shù)而所有其他的數(shù) an 都是正整數(shù)。可依樣定義出更長的表達(dá)式。如果部分分子（partial numerator）和部分分母（partial denominator）允許假定任意的值，在某些上下文中可以包含函數(shù)，則最終的表達(dá)式是廣義連分?jǐn)?shù)。在需要把上述標(biāo)準(zhǔn)形式與廣義連分?jǐn)?shù)相區(qū)別的時(shí)候，可稱它為簡單或正規(guī)連分?jǐn)?shù)，或稱為是規(guī)范形式的一個(gè)數(shù)的連分?jǐn)?shù)表示是有限的，當(dāng)且僅當(dāng)這個(gè)數(shù)是有理數(shù)。 “簡單”有理數(shù)的連分?jǐn)?shù)表示是簡短的。 任何有理數(shù)的連分?jǐn)?shù)表示是唯一的，如果它沒有尾隨的 1。（但是 a0; a1, . an, 1 = a0; a1, . an + 1。

24、） 無理數(shù)的連分?jǐn)?shù)表示是唯一的。 連分?jǐn)?shù)的項(xiàng)將會(huì)重復(fù)，當(dāng)且僅當(dāng)它是一個(gè)二次無理數(shù)（即整數(shù)系數(shù)的二次方程的實(shí)數(shù)解）的連分?jǐn)?shù)表示。 數(shù) x 的截?cái)噙B分?jǐn)?shù)表示很早產(chǎn)生 x 的在特定意義上“最佳可能”的有理數(shù)逼近。 第67頁，共152頁。連分?jǐn)?shù)逼近意義1、精度保留2、避免浮點(diǎn)運(yùn)算3、無理數(shù)的表示唯一4、研究連分?jǐn)?shù)的動(dòng)機(jī)源于想要有實(shí)數(shù)在“數(shù)學(xué)上純粹”的表示。求解歐幾里德變體！第68頁，共152頁。連分?jǐn)?shù)逼近 第69頁，共152頁。數(shù)據(jù)結(jié)構(gòu)Soul !第70頁，共152頁。數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)?數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運(yùn)行或者存儲(chǔ)效率的算法。數(shù)據(jù)

25、結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān)。 數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)科學(xué)界至今沒有標(biāo)準(zhǔn)的定義。個(gè)人根據(jù)各自的理解而有不同的表述方法：Sartaj Sahni 在他的數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用一書中稱：“數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)對(duì)象，以及存在于該對(duì)象的實(shí)例和組成實(shí)例的數(shù)據(jù)元素之間的各種聯(lián)系。這些聯(lián)系可以通過定義相關(guān)的函數(shù)來給出?！彼麑?shù)據(jù)對(duì)象（data object）定義為“一個(gè)數(shù)據(jù)對(duì)象是實(shí)例或值的集合”。Clifford A.Shaffer 在數(shù)據(jù)結(jié)構(gòu)與算法分析一書中的定義是：“數(shù)據(jù)結(jié)構(gòu)是 ADT（抽象數(shù)據(jù)類型 Abstract Data Type） 的物理實(shí)現(xiàn)?！盠obert L.Kruse 在數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)一書

26、中，將一個(gè)數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)過程分成抽象層、數(shù)據(jù)結(jié)構(gòu)層和實(shí)現(xiàn)層。其中，抽象層是指抽象數(shù)據(jù)類型層，它討論數(shù)據(jù)的邏輯結(jié)構(gòu)及其運(yùn)算，數(shù)據(jù)結(jié)構(gòu)層和實(shí)現(xiàn)層討論一個(gè)數(shù)據(jù)結(jié)構(gòu)的表示和在計(jì)算機(jī)內(nèi)的存儲(chǔ)細(xì)節(jié)以及運(yùn)算的實(shí)現(xiàn)。第71頁，共152頁。數(shù)據(jù)結(jié)構(gòu)為什么要使用數(shù)據(jù)結(jié)構(gòu)?1、便于理清結(jié)構(gòu)，易于表示出一個(gè)實(shí)體的內(nèi)部屬性與外部聯(lián)系。2、更好利用實(shí)體特性，從而為算法高效鋪路。3、強(qiáng)有力的數(shù)據(jù)結(jié)構(gòu)，能夠取代算法的優(yōu)勢。第72頁，共152頁。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的基本類型：1、順序表2、鏈表3、廣義表4、樹5、圖6、串第73頁，共152頁。順序表順序表是在內(nèi)存上開辟的連續(xù)片段，每個(gè)元素單元擁有固定大小，以此組織形成的數(shù)據(jù)結(jié)構(gòu)。

27、優(yōu)點(diǎn)：1、隨機(jī)存取2、索引唯一3、結(jié)構(gòu)簡單第74頁，共152頁。順序表一般應(yīng)用：1、寄存數(shù)組（包括棧和隊(duì)列）2、哈希數(shù)組3、樹狀數(shù)組第75頁，共152頁。寄存數(shù)組這是我們最常見的順序表表現(xiàn)方式，一般的大數(shù)據(jù)量程序，如果不能有邊讀邊處理的方法，就需要首先保留所有的輸入，從而能夠在而后的過程中進(jìn)行處理。主要應(yīng)用：1、各類算法的線性預(yù)處理2、保留線性邏輯關(guān)系3、記憶化輔助第76頁，共152頁。寄存數(shù)組優(yōu)點(diǎn)：1、靜態(tài)2、隨機(jī)3、高效缺點(diǎn)：1、插入與刪除操作效率極度低下2、內(nèi)存分配不靈活技巧：1、滿足遞推與DP內(nèi)存需求滾動(dòng)數(shù)組2、滿足圖的快速判重化行為數(shù) 狀態(tài)壓縮第77頁，共152頁。哈希數(shù)組什么是哈希

28、？從廣義上說哈希是一種鍵值對(duì)應(yīng)的操作，是從數(shù)域到值域的一一映射，也就是我們通常稱其為哈希函數(shù)的由來。為什么哈希表可以用數(shù)組實(shí)現(xiàn)？數(shù)組滿足哈希的3個(gè)必要條件：1、鍵index2、值value3、鍵值映射（index-value）O（1）第78頁，共152頁。哈希數(shù)組散列函數(shù)的選用一般情況下我們使用哈希數(shù)組，采用的是開放散列策略，也就是說內(nèi)存與鍵是一一對(duì)應(yīng)，即hashkey=value,在對(duì)于key值要求不大的情況下是很好的選擇。然而當(dāng)要求的key很大時(shí)該怎么辦，此時(shí)就應(yīng)該選用一個(gè)好的映射函數(shù)使hashf(key)=value，且f(key)的值必定均勻分布在映射區(qū)間內(nèi)。當(dāng)然要找到這樣的函數(shù)是十分

29、困難的，我們無法了解到數(shù)據(jù)的具體信息，因此一般的f(key)為key%p，p為一個(gè)質(zhì)數(shù)，結(jié)合數(shù)論知識(shí)，我們可以知道當(dāng)gcd(key,p)=1時(shí)，key是一個(gè)循環(huán)群生成元，使用這個(gè)性質(zhì)，我們可以少了許多因大多數(shù)沖突而引發(fā)避免策略造成的效率問題。第79頁，共152頁。哈希數(shù)組HDU 2192題意 ：遞增的序列組成一個(gè)集合 請問至少有幾個(gè)？思路？第80頁，共152頁。哈希數(shù)組出現(xiàn)次數(shù)最多的數(shù)，決定了能分成的最少群落！實(shí)現(xiàn)方式？哈希！散列函數(shù)如何刻畫？思考！根據(jù)問題的輸入規(guī)模，最大104個(gè)數(shù)，因此選取大于104的質(zhì)數(shù)作為散列函數(shù)的參數(shù)，令f(key)=key%p還有什么問題？思考出現(xiàn)沖突！第81頁，共

30、152頁。哈希數(shù)組解決方案：1、線性掃描法2、二次線性掃描3、桶鏈問題完美解決，注意各個(gè)結(jié)點(diǎn)在不同解決方案下添加的相關(guān)變量。第82頁，共152頁。樹狀數(shù)組首先我們得知道一個(gè)問題,那就是線段樹的作用并不只是用來存儲(chǔ)線段的,也可以存儲(chǔ)點(diǎn)的值等等.對(duì)于靜態(tài)的線段樹,空間上需要的數(shù)組有:當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)值,左兒子編號(hào),右兒子編號(hào).至少這么三個(gè)數(shù)組.而在時(shí)間上雖然是NlogN的復(fù)雜度,但是系數(shù)很大.實(shí)現(xiàn)起來的時(shí)候編程復(fù)雜度大,空間復(fù)雜度大,時(shí)間效率也不是很理想.第83頁，共152頁。有!那就是樹狀數(shù)組!那么是否有更好的解決方法呢?第84頁，共152頁。樹狀數(shù)組先看一個(gè)例題:數(shù)列操作: 給定一個(gè)初始值都為0

31、的序列,動(dòng)態(tài)地修改一些位置上的數(shù)字,加上一個(gè)數(shù),減去一個(gè)數(shù),或者乘上一個(gè)數(shù),然后動(dòng)態(tài)地提出問題,問題的形式是求出一段數(shù)字的和.第85頁，共152頁。樹狀數(shù)組如果直接做的話,修改的復(fù)雜度是O(1),詢問的復(fù)雜度是O(N),M次詢問的復(fù)雜度是M*N.M,N的范圍可以有100000以上第86頁，共152頁。用線段樹可以這樣解:若要維護(hù)的序列范圍是0.5,先構(gòu)造下面的一棵線段樹:第87頁，共152頁。樹狀數(shù)組可以看出,這棵樹的構(gòu)造用二分便可以實(shí)現(xiàn).復(fù)雜度是2*N.每個(gè)結(jié)點(diǎn)用數(shù)組a來表示該結(jié)點(diǎn)所表示范圍內(nèi)的數(shù)據(jù)之和.修改一個(gè)位置上數(shù)字的值,就是修改一個(gè)葉子結(jié)點(diǎn)的值,而當(dāng)程序由葉子結(jié)點(diǎn)返回根節(jié)點(diǎn)的同時(shí)順便

32、修改掉路徑上的結(jié)點(diǎn)的a數(shù)組的值. 對(duì)于詢問的回答,可以直接查找i.j范圍內(nèi)的值,遇到分叉時(shí)就兵分兩路,最后在合起來.也可以先找出0.i-1的值和0.j的值,兩個(gè)值減一減就行了.后者的實(shí)際操作次數(shù)比前者小一些.這樣修改與維護(hù)的復(fù)雜度是logN.詢問的復(fù)雜度也是logN,對(duì)于M次詢問,復(fù)雜度是MlogN.第88頁，共152頁。樹狀數(shù)組用樹狀數(shù)組!然而不難發(fā)現(xiàn),線段樹的編程復(fù)雜度大,空間復(fù)雜度大,時(shí)間效率也不高.怎么辦第89頁，共152頁。樹狀數(shù)組下圖中的C數(shù)組就是樹狀數(shù)組,a數(shù)組是原數(shù)組先自己研究一下這個(gè)東西第90頁，共152頁。樹狀數(shù)組可以發(fā)現(xiàn)這些規(guī)律C1=a1C2=a1+a2C3=a3C4=a

33、1+a2+a3+a4C5=a5C8=a1+a2+a3+a4+a5+a6+a7+a8C2n=a1+a2+.+a2n第91頁，共152頁。樹狀數(shù)組對(duì)于序列a，我們設(shè)一個(gè)數(shù)組C定義Ci = ai 2k + 1 + + ai，k為i在二進(jìn)制下末尾0的個(gè)數(shù)。K的計(jì)算可以這樣:2k=x and (x xor (x-1) 以6為例 (6)10=(0110)2xor 6-1=(5)10=(0101)2 (0011)2and (6)10=(0110)2 (0010)2第92頁，共152頁。樹狀數(shù)組function Lowbit(x: Integer): Integer;begin Lowbit := x and

34、 (x xor (x 1);end;若要修改ai的值,則C數(shù)組的修改是:Procedure change(k,delta:integer);Begin while k0 do begin t:=t+ck; k:=k-lowbit(k); end; getsum:=t;End;第94頁，共152頁。樹狀數(shù)組對(duì)于剛才的一題,每次修改與詢問都是對(duì)C數(shù)組做處理.空間復(fù)雜度有3N降為N,時(shí)間效率也有所提高.編程復(fù)雜度更是降了不少.在很多的情況下,線段樹都可以用樹狀數(shù)組實(shí)現(xiàn).凡是能用樹狀數(shù)組的一定能用線段樹.當(dāng)題目不滿足減法原則的時(shí)候,就只能用線段樹,不能用樹狀數(shù)組.例如數(shù)列操作如果讓我們求出一段數(shù)字中最

35、大或者最小的數(shù)字,就不能用樹狀數(shù)組了.第95頁，共152頁。鏈表鏈表是內(nèi)存中不連續(xù)塊鏈接而成的數(shù)據(jù)結(jié)構(gòu)，本著使用多少分配多少的原則，極大地節(jié)約和利用了內(nèi)存，是一種十分基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)。優(yōu)勢：1、動(dòng)態(tài)分配2、快速刪除與插入3、節(jié)省空間第96頁，共152頁。鏈表缺點(diǎn)：1、查找效率低下2、動(dòng)態(tài)分配結(jié)點(diǎn)調(diào)用操作系統(tǒng)實(shí)現(xiàn)，導(dǎo)致空間分配效率消耗一種對(duì)空間的優(yōu)化：內(nèi)存靜態(tài)化！一般應(yīng)用1、桶2、跳躍表第97頁，共152頁。桶一般用做哈希的沖突避免策略，使用桶結(jié)構(gòu)存儲(chǔ)在同一沖突域下的數(shù)據(jù)，作為鍵值的擴(kuò)展?；鶖?shù)數(shù)排序的輔助結(jié)構(gòu)。第98頁，共152頁。跳躍表可以看做是鏈表結(jié)構(gòu)最優(yōu)秀的應(yīng)用，使用跳躍表有著令人震撼的效率

36、，對(duì)查詢、刪除和添加的操作均為O（logn）的復(fù)雜度。利用了鏈表自身的特點(diǎn)，以較小的空間代價(jià)提升了自身的性能。使用了概率算法，使效率堪與AVL、RB-Tree等BST相媲美。相比而言，極低的編程復(fù)雜度！有什么理由可以不去掌握呢？第99頁，共152頁。跳躍表跳躍表由多條鏈構(gòu)成（S0，S1，S2 ，Sh），且滿足如下三個(gè)條件：每條鏈必須包含兩個(gè)特殊元素：+ 和 -S0包含所有的元素，并且所有鏈中的元素按照升序排列。每條鏈中的元素集合必須包含于序數(shù)較小的鏈的元素集合，即：53 53 53 45 45 37 30 30 30 29 15 11 11 11 11 - - - - + + + + S0 S

37、1 S2 S3 跳躍表的實(shí)例第100頁，共152頁。跳躍表之查找目的：在跳躍表中查找一個(gè)元素 x在跳躍表中查找一個(gè)元素x，按照如下幾個(gè)步驟進(jìn)行：從最上層的鏈（Sh）的開頭開始假設(shè)當(dāng)前位置為p，它向右指向的節(jié)點(diǎn)為q（p與q不一定相鄰），且q的值為y。將y與x作比較x=y輸出查詢成功，輸出相關(guān)信息xy從p向右移動(dòng)到q的位置xy從p向下移動(dòng)一格如果當(dāng)前位置在最底層的鏈中（S0），且還要往下移動(dòng)的話，則輸出查詢失敗53 53 53 45 45 37 30 30 30 29 15 11 11 11 11 - - - - + + + + 查詢元素53的全過程S0 S1 S2 S3 查找成功！第101頁，共

38、152頁。跳躍表之插入目的：在跳躍表中插入一個(gè)元素 x插入操作由兩部分組成：查找插入的位置和插入對(duì)應(yīng)元素。為了確定插入的“列高”，我們引入一個(gè)隨機(jī)決策模塊：產(chǎn)生一個(gè)0到1的隨機(jī)數(shù)rr random()如果r小于一個(gè)概率因子P，則執(zhí)行方案A，if r dist(right(A)，交換left(A) 和right(A)最后，由于right(A) 的距離可能發(fā)生改變，我們必須更新A的距離：dist(A) dist(right(A) + 1不難驗(yàn)證，經(jīng)這樣合并后的樹C符合性質(zhì)1和性質(zhì)2，因此是一棵左偏樹。至此左偏樹的合并就完成了。第123頁，共152頁。左偏樹合并操作都是一直沿著兩棵左偏樹的最右路徑進(jìn)

39、行的。一棵N個(gè)節(jié)點(diǎn)的左偏樹，最右路徑上最多有 log(N+1) 個(gè)節(jié)點(diǎn)。因此，合并操作的時(shí)間復(fù)雜度為：O(log N1 + log N2) = O(log N)合并操作的代碼如下：Function Merge(A, B)If A = NULL Then return BIf B = NULL Then return AIf key(B) dist(left(A) Thenswap(left(A), right(A)If right(A) = NULL Then dist(A) 0Else dist(A) dist(right(A) + 1return AEnd Function第124頁，共1

40、52頁。左偏樹左偏樹的特點(diǎn)：時(shí)空效率高編程復(fù)雜度低左偏樹的應(yīng)用：可并堆優(yōu)先隊(duì)列第125頁，共152頁。左偏樹HDU 1512題意：剛開始所有的猴子自成一群且互相都不認(rèn)識(shí)，他們互相認(rèn)識(shí)當(dāng)且僅當(dāng)他們各自群中最強(qiáng)的猴子互相打了一場，體力各減為一半。問最后這群猴子中體力最強(qiáng)猴子的體力是多少思路如何？第126頁，共152頁。左偏樹并查？可行，但只能作為輔助手段。優(yōu)先隊(duì)列+并查？O（nlogn）的合并效率實(shí)在不敢恭維很好。左偏樹開始發(fā)揮了效力了！第127頁，共152頁。左偏樹步驟：使用并查集（這里其實(shí)準(zhǔn)確來說應(yīng)該是一種記錄父結(jié)點(diǎn)編號(hào)的數(shù)組）記錄各結(jié)點(diǎn)在各自堆中的父結(jié)點(diǎn)查詢兩只猴子所在堆的根結(jié)點(diǎn)，如果兩只猴

41、子根結(jié)點(diǎn)相同，則不必打架，否則，取各自堆中最大元素（也就是根結(jié)點(diǎn)）打一場打架，此時(shí)先讓各自堆中根的左右兒子指向本身，再對(duì)左右兒子進(jìn)行合并生成新樹（即pop操作）并適當(dāng)修改父結(jié)點(diǎn)數(shù)組，令根結(jié)點(diǎn)值減半后與新樹再次合并，并適時(shí)修改父結(jié)點(diǎn)數(shù)組（即push操作），再將兩個(gè)堆中的根進(jìn)行合并（即unition操作）。是不是很簡單的實(shí)現(xiàn)？第128頁，共152頁。斜堆如何對(duì)左偏樹進(jìn)行優(yōu)化？思考！我們注意到在左偏樹中必須要有距離的概念，但我們可以發(fā)現(xiàn)一個(gè)性質(zhì)，如果每次合并都向右進(jìn)行，每次完成后將右邊的結(jié)點(diǎn)甩到左邊，不正好符合了左偏的性質(zhì)么？很好去掉距離，提高效率，優(yōu)化的王道！不足（單次合并可能退化到O(n)，但實(shí)

42、際效果上，兩者都差不多）第129頁，共152頁。AC自動(dòng)機(jī)AC自動(dòng)機(jī)是由Aho和Corasick提出的數(shù)據(jù)結(jié)構(gòu),是對(duì)Trie樹的一種改造，是對(duì)find操作的修正，也是多模式串匹配的基本實(shí)現(xiàn)！HDU 2222題意給你N個(gè)關(guān)鍵字,以及一句描述,問有多少個(gè)關(guān)鍵字在這句描述中出現(xiàn)?思路?第130頁，共152頁。AC自動(dòng)機(jī)采用普通方法？O（Nnm）m=50,n=1000000,N=10000黃花菜都涼了KMP?O(N(m+n)?就這點(diǎn)優(yōu)化？塞牙縫都不夠那怎么辦！AC自動(dòng)機(jī)！O（Nm+n）強(qiáng)大！第131頁，共152頁。AC自動(dòng)機(jī)步驟將所有關(guān)鍵字塞入Trie好了，現(xiàn)在我們已經(jīng)有一棵Trie了，但這還不夠，我

43、們還要在Trie上引入一個(gè)很強(qiáng)大的東西：失敗指針或者說shift數(shù)組或者說Next函數(shù) .你愛怎么叫怎么叫吧，反正就是KMP的精華所在，這也是我為什么叫你看KMP的原因。KMP中我們用兩個(gè)指針i和j分別表示，Ai-j+ 1.i與B1.j完全相等。也就是說，i是不斷增加的，隨著i的增加j相應(yīng)地變化，且j滿足以Ai結(jié)尾的長度為j的字符串正好匹配B串的前 j個(gè)字符，當(dāng)Ai+1Bj+1，KMP的策略是調(diào)整j的位置（減小j值）使得Ai-j+1.i與B1.j保持匹配且新的Bj+1恰好與Ai+1匹配（從而使得i和j能繼續(xù)增加）。Trie樹上的失敗指針與此類似。第132頁，共152頁。AC自動(dòng)機(jī)假設(shè)有一個(gè)節(jié)點(diǎn)

44、k，他的失敗指針指向j。那么k,j滿足這個(gè)性質(zhì)：設(shè)root到j(luò)的距離為n，則從k之上的第n個(gè)節(jié)點(diǎn)到k所組成的長度為n的單詞，與從root到j(luò)所組成的單詞相同。那么我們要怎樣構(gòu)建這個(gè)東西呢？其實(shí)我們可以用一個(gè)簡單的BFS搞定這一切。對(duì)于每個(gè)節(jié)點(diǎn)，我們可以這樣處理：設(shè)這個(gè)節(jié)點(diǎn)上的字母為C，沿著他父親的失敗指針走，直到走到一個(gè)節(jié)點(diǎn)，他的兒子中也有字母為C的節(jié)點(diǎn)。然后把當(dāng)前節(jié)點(diǎn)的失敗指針指向那個(gè)字目也為C的兒子。如果一直走到了root都沒找到，那就把失敗指針指向root最開始，我們把root加入隊(duì)列(root的失敗指針顯然指向自己)，這以后我們每處理一個(gè)點(diǎn)，就把它的所有兒子加入隊(duì)列，直到搞完。好了，現(xiàn)

45、在我們有了一棵帶失敗指針的Trie了 ！可以開始進(jìn)行AC自動(dòng)機(jī)了！第133頁，共152頁。AC自動(dòng)機(jī)一開始，Trie中有一個(gè)指針t1指向root，待匹配串(也就是“文章”)中有一個(gè)指針t2指向串頭。接下來的操作和KMP很相似：如果t2指向的字母，是Trie樹中，t1指向的節(jié)點(diǎn)的兒子，那么t2+1,t1改為那個(gè)兒子的編號(hào)，否則t1順這當(dāng)前節(jié)點(diǎn)的失敗指針向上找，直到t2是t1的一個(gè)兒子，或者t1指向根。如果t1路過了一個(gè)綠色的點(diǎn)，那么以這個(gè)點(diǎn)結(jié)尾的單詞就算出現(xiàn)過了?；蛘呷绻鹴1所在的點(diǎn)可以順著失敗指針走到一個(gè)綠色點(diǎn)，那么以那個(gè)綠點(diǎn)結(jié)尾的單詞就算出現(xiàn)過了。本題要注意的是必須在描述串后面添加特殊符號(hào)，

46、否則將忽略對(duì)完全匹配關(guān)鍵字的統(tǒng)計(jì)。注意：BFS尋找失敗指針的過程，是一個(gè)自我匹配的過程。第134頁，共152頁。AC自動(dòng)機(jī)特點(diǎn)：多模式匹配的良方，一次自我適配后，對(duì)任意文章的匹配均是線性復(fù)雜度。編程復(fù)雜度較低。使用方便，居家旅行之必備！第135頁，共152頁。圖圖的結(jié)構(gòu)是樹結(jié)構(gòu)的拓展，但在實(shí)現(xiàn)基本以數(shù)組的形式進(jìn)行，在本質(zhì)上來說所有的數(shù)據(jù)結(jié)構(gòu)都是互相滲透交融的，所謂大道行簡，只有掌握了本質(zhì)，才能以不變應(yīng)萬變！基本表示：鄰接陣鄰接表由于上部分內(nèi)容已經(jīng)有所涉獵，這里就不再提過了第136頁，共152頁。串什么是串？串是由字符所組成的有限序列，我們只關(guān)心串的字符屬性，而不關(guān)心其數(shù)值屬性。串有著十分明顯的

47、邏輯結(jié)構(gòu)，前驅(qū)后繼都是固定的，不得隨意更改！關(guān)于字符串的處理一般而言都是ICPC的中檔題目，如果使用模擬或者暴力方法，一般來說都是無效的。應(yīng)用結(jié)構(gòu)：后綴數(shù)組第137頁，共152頁。后綴數(shù)組什么是后綴數(shù)組？對(duì)于長度為len的字符串str，從位置i開始至len的所有字符序列稱為i的后綴后綴數(shù)組（SA）保存的就是這些后綴序列的排序后的開頭位置.Rank數(shù)組是SA的反函數(shù)，也就是說Ranki保存的是從位置i開始的后綴在所有后綴中的名次.第138頁，共152頁。后綴數(shù)組如何利用這種結(jié)構(gòu)性質(zhì)？我們還需要計(jì)算一個(gè)輔助的工具最長公共前綴（Longest Common Prefix）!對(duì)兩個(gè)字符串u,v 定義函

48、數(shù)lcp(u,v)=maxi|u=iv，也就是從頭開始順次比較u 和v 的對(duì)應(yīng)字符，對(duì)應(yīng)字符持續(xù)相等的最大位置，稱為這兩個(gè)字符串的最長公共前綴。對(duì)正整數(shù)i,j 定義LCP(i,j)=lcp(Suffix(SAi),Suffix(SAj)，其中i,j 均為1 至n 的整數(shù)。LCP(i,j)也就是后綴數(shù)組中第i 個(gè)和第j 個(gè)后綴的最長公共前綴的長度。關(guān)于LCP 有兩個(gè)顯而易見的性質(zhì)：性質(zhì)2.1 LCP(i,j)=LCP(j,i)性質(zhì)2.2 LCP(i,i)=len(Suffix(SAi)=n-SAi+1這兩個(gè)性質(zhì)的用處在于，我們計(jì)算LCP(i,j)時(shí)只需要考慮ij時(shí)可交換i,j，i=j時(shí)可以直接輸

49、出結(jié)果n-SAi+1。第139頁，共152頁。后綴數(shù)組直接根據(jù)定義，用順次比較對(duì)應(yīng)字符的方法來計(jì)算LCP(i,j)顯然是很低效的，時(shí)間復(fù)雜度為O(n)，所以我們必須進(jìn)行適當(dāng)?shù)念A(yù)處理以降低每次計(jì)算LCP的復(fù)雜度。經(jīng)過仔細(xì)分析，我們發(fā)現(xiàn)LCP 函數(shù)有一個(gè)非常好的性質(zhì)：設(shè)ij，則LCP(i,j)=minLCP(k-1,k)|i+1kj （LCP Theorem）根據(jù)LCP Theorem得出必然的一個(gè)推論：LCP Corollary 對(duì)ijk，LCP(j,k)LCP(i,k)。第140頁，共152頁。后綴數(shù)組定義一維數(shù)組height，令heighti=LCP(i-1,i)，11 且Ranki1，一定有hihi-1-1。根據(jù)性質(zhì)3，可以令i從1 循環(huán)到n按照如下方法依次算出hi：若Ranki=1，則h