區塊鏈公共前綴性質

⑴ 分布式共識包含哪三種方法

PoW 、PoS 、DPOW都是什麼意思？
說到區塊鏈，我們必然會談及它的共識機制。不了解區塊鏈的共識機制，就無法理解區塊鏈的真正意義。那麼，今日份的區塊鏈的共識機制了解一下？
共識機制是什麼？
什麼是共識？直取它的字面意思，就是"共同的認識".
人與人是不同的，這種不同不僅體現在身材、長相、能力，更體現在文化、觀點、想法、利益訴求等等方面。
共識，簡而言之，就是一個群體的成員在某一方面達成的一致意見。
我們了解到，信任是社會運轉中的一大痛點，銀行有自己的信用體系，過去的金融體系服務於只服務於極少的企業家，因為建立信用體系耗資巨大。後來支付寶有了芝麻信用，信用已經關繫到生活的很多方面，信用卡額度、花唄額度，芝麻信用高出國還可以免簽。我們正享受著信用給我們帶來的便捷。
區塊鏈本質是去中心化，去中心化的核心是共識機制，區塊鏈上的共識機制主要解決由誰來構造區塊，以及如何維護區塊鏈統一的問題。
區塊鏈共識機制的目標是使所有的誠實節點保存一致的區塊鏈視圖，同時滿足兩個性質：
1）一致性：所有誠實節點保存的區塊鏈的前綴部分完全相同。
2）有效性：由某誠實節點發布的信息終將被其他所有誠實節點記錄在自己的區塊鏈中。
區塊鏈的自信任主要體現於分布於區塊鏈中的用戶無須信任交易的另一方，也無須信任一個中心化的機構，只需要信任區塊鏈協議下的軟體系統即可實現交易。
共識機制是什麼？PoW 、PoS 、DPOW都是什麼意思？
共識機制的必要性？
分布式系統中，多個主機通過非同步通信方式組成網路集群。在這樣的一個非同步系統中，需要主機之間進行狀態復制，以保證每個主機達成一致的狀態共識。錯誤信息可能出現在非同步系統內並不斷傳播，因此需要在默認不可靠的非同步網路中定義容錯協議，以確保各主機達成安全可靠的狀態共識，這就是共識機制誕生的必要性。
這種自信任的前提是區塊鏈的共識機制（consensus），即在一個互不信任的市場中，要想使各節點達成一致的充分必要條件是每個節點出於對自身利益最大化的考慮，都會自發、誠實地遵守協議中預先設定的規則，判斷每一筆記錄的真實性，最終將判斷為真的記錄記入區塊鏈之中。attachments-2018-08-9yY7VRHa5b738e3d96021.jpg
換句話說，如果各節點具有各自獨立的利益並互相競爭，則這些節點幾乎不可能合謀欺騙你，而當節點們在網路中擁有公共信譽時，這一點體現得尤為明顯。區塊鏈技術正是運用一套基於共識的數學演算法，在機器之間建立"信任"網路，從而通過技術背書而非中心化信用機構來進行全新的信用創造。
當今區塊鏈的幾種共識機制介紹
區塊鏈上的共識機制有多種，但任何一種都不是完美無缺，或者說適用於所有應用場景的。
PoW 工作量證明
整個系統中每個節點為整個系統提供計算能力（簡稱算力），通過一個競爭機制，讓計算工作完成最出色的節點獲得系統的獎勵，即完成新生成貨幣的分配，簡單理解就是多勞多得，bitcoin、LTC等貨幣型區塊鏈就應用POW機制。
優點
完全去中心化節點自由進出，演算法簡單，容易實現破壞系統花費的成本巨大，只要網路破壞者的算力不超過網路總算力的50%,網路的交易狀態就能達成一致
缺點
浪費能源，這是最大的缺點區塊的確認時間難以縮短，如bitcoin每秒只能做7筆交易，不適合商業應用新的區塊鏈必須找到一種不同的散列演算法，否則就會面臨bitcoin的算力攻擊對節點的性能網路環境要求高容易產生分叉，需要等待多個確認無法達成最終一致性
PoS 權益證明
也稱股權證明，類似於你把財產存在銀行，這種模式會根據你持有加密貨幣的數量和時間，分配給你相應的利息。
優點
對節點性能要求低，達成共識時間短
缺點
沒有最終一致性，需要檢查點機制來彌補最終性
DPOW 委託股權證明
DPOW是 PoS 的進化方案，在常規 PoW和 PoS 中，任何一個新加入的區塊，都需要被整個網路所有節點做確認，非常影響效率。
DPoS則類似於現代董事會的投票機制，通過選舉代表來進行投票和決策。被選舉出的n個記賬節點來做新區塊的創建、驗證、簽名和相互監督，這樣就極大地減少了區塊創建和確認所需要消耗的時間和算力成本。
優點
大幅縮小參與驗證和記賬節點的數量，可以達到秒級的共識驗證
缺點
犧牲了去中心化的概念，不適合公有鏈
PBFT 實用拜占庭容錯
實用拜占庭容錯機制是一種採用"許可投票、少數服從多數"來選舉領導者並進行記賬的共識機制，該共識機制允許拜占庭容錯，允許強監督節點參與，具備許可權分級能力，性能更高，耗能更低，而且每輪記賬都會由全網節點共同選舉領導者，允許33%的節點作惡，容錯率為33%.實用拜占庭容錯特別適合聯盟鏈的應用場景。
優點
會背離中心化，加密貨幣的存在及獎勵機制會產生馬太效應，讓社區中的窮者更窮，富者更富共識效率高，可實現高頻交易
缺點
當系統只剩下33%的節點運行時，系統會停止運行
dBFT 授權拜占庭容錯
這種機制是用權益來選出記賬人，然後記賬人之間通過拜占庭容錯演算法達成共識。授權拜占庭容錯機制最核心的一點，就是最大限度地確保系統的最終性，使區塊鏈能夠適用於真正的金融應用場景。
優點
專業化的記賬人可以容忍任何類型的錯誤記賬由多人協同完成，每一個區塊都有最終性，不會分叉演算法的可靠性有嚴格的數學證明
缺點
當三分之一或以上記賬人停止工作後，系統將無法提供服務當三分之一或以上記賬人聯合作惡，可能會使系統出現分叉
Pool 驗證池
基於傳統的分布式一致性技術，加上數據驗證機制。
優點
不需要加密貨幣也可以工作，在成熟的分布式一致性演算法（Pasox、Raft）基礎上，實現秒級共識驗證。
缺點
去中心化程度不如bitcoin,更適合多方參與的多中心商業模式。
Paxos
這是一種傳統的分布式一致性演算法，是一種基於選舉領導者的共識機制。領導者節點擁有絕對許可權，並允許強監督節點參與，其性能高，資源消耗低。所有節點一般有線下准入機制，但選舉過程中不允許有作惡節點，不具備容錯性。
Paxos演算法中將節點分為三種類型：
proposer:提出一個提案，等待大家批准為結案。往往是客戶端擔任該角色
acceptor:負責對提案進行投票。往往是服務端擔任該角色
learner:被告知結案結果，並與之統一，不參與投票過程。可能為客戶端或服務端
Paxos 能保證在超過50%的正常節點存在時，系統能達成共識。
瑞波共識機制
瑞波共識演算法使一組節點能夠基於特殊節點列表形成共識，初始特殊節點列表就像一個俱樂部，要接納一個新成員，必須由該俱樂部51%的會員投票通過。共識遵循這些核心成員的"51%權利",外部人員則沒有影響力。由於該俱樂部由中心化開始，它將一直是中心化的，而如果它開始腐化，股東們什麼也做不了。與bitcoin及Peercoin一樣，瑞波系統將股東們與其投票權隔開，因此，它比其他系統更中心化。
Peercoin
Peercoin（點點幣，PPC），混合了POW工作量證明及POS權益證明方式，其中POW主要用於發行貨幣，未來預計隨著挖礦難度上升，產量降低，系統安全主要由POS維護。
在區塊鏈網路中，由於應用場景的不同，所設計的目標各異，不同的區塊鏈系統採用了不同的共識演算法。每種共識演算法都不是完美的，都有其優點和局限性。
區塊鏈解決了在不可信信道上傳輸可信信息、價值轉移的問題，而共識機制解決了區塊鏈如何分布式場景下達成一致性的問題。
雖然區塊鏈目前還處於發展的早期，行業發展還面臨著一些阻礙，但社會已經足夠多地認識到區塊鏈的價值，區塊鏈發展的腳步絕不會停滯不前，行業發展也定會找到突破阻礙的方法。

⑵ 區塊鏈的應用場景有哪些

在甲骨文公司的網站上列出了區塊鏈的十類行業應用場景

包括金融、生產、教育、傳媒、娛樂、政府、零售商務、健康、醫療、供應鏈、保險、公共事業。是不是很高大上？但是我想說的是這些應用場景，在真正高能的區塊鏈應用面前，這些應用場景只能先躲到牆角，瑟瑟發抖。

現在區塊鏈真正高能的應用場景是龐氏應用，俗稱「龐氏騙局」。是智能合約型的錢寶、是滾動入金出金的區塊鏈游戲、是以交易為目的的ICO、是全球通用的養老金平台。

龐氏騙局是我們人類最古老的應用場景之一，在互聯網出現之後，龐氏騙局已經升級了一次「互聯網+」，即「互聯網+龐氏騙局」。互聯網為龐氏騙局賦能，所以發生了類似錢寶百億級別的事件，在互聯網時代以前，很少有這么大規模的龐氏騙局，通過互聯網賦能，通過手機APP入金出金，最後滾動幾年，達到了百億級別的規模。

互聯網實現了打破地域限制，物理限制，資金流動限制，傳播限制。只要有手機就能玩錢寶APP，人人參與，人人入金，人人出金，涉案人數據說達到百萬級別，相對而言，還停留在線下拉人頭的傳銷（龐氏騙局1.0），天天開會洗腦不能停，使用暴力非法手段，簡直弱爆了。隨著區塊鏈技術的興起，使用「區塊鏈+」賦能的龐氏騙局，已經不能用如虎添翼來形容了，簡直是如雞變虎。跟互聯網一樣，「區塊鏈+」技術對應用場景的提升是實打實，龐氏騙局在「互聯網+」的二代基礎進一步升級，因為有重大的場景提升和改進突破，變成龐氏騙局3.0，其特徵主要在以下幾方面體現：

1、去中心化，無首腦化。區塊鏈的智能合約是自動運行的，不需要人為干預，也無法被人為中斷。代碼規則寫死，無法篡改。在場景改進上，解決了幾千年來，龐氏騙局最大的痛點，即首腦跑路的問題。因為首腦是程序，是代碼，區塊鏈的程序可以做到永久存在，沒有任何人可以刪掉它。我認為這是最大的突破。這個虛擬的首腦是一直在的，跑不掉，也不會跑，也不會改，規則永遠不變，堅持龐氏路線一百年一千年一萬年。可能會有人說，智能合約是可以迭代的，還可以做手腳留後門。沒錯，但是也可以做到不需要迭代，即使迭代，也是透明可見的，留了後門，也是一目瞭然的。這就是區塊鏈智能合約的特點，你在上面作弊，等於在老師眼皮下拿出小抄，這樣的智能合約，上線了也沒人參與。所以經過技術審查、驗證，沒有後門，公平規則，不可撤銷的智能合約，可以使用區塊鏈技術實現。這樣的可靠性，一次驗證通過，永久不變。這就是智能合約的確定性，一段程序，一個字元的代碼都不變，運行一百萬次一萬億次，結果都是一致的確定性。

2、過程透明化。入金人數、地址賬號、數額、時間；出金人數、地址賬號、數額、時間；全部可見。區塊鏈具有公共的賬本功能，全世界人人可以查看，人人查看的賬本數據完全一致。錢寶為什麼爆倉？因為我們看不到他的後台賬號，每天進去多少錢，出來多少錢，具體的每一筆明細。這樣在入金之前就能看到兌付能力的評估，而且這個評估結果也是絕對確定性的，即不會在你入金之後發生變化。

3、徹底匿名化。你如果聽過什麼零知識證明技術。這部分就可以跳過。簡單來說，以前我們在數學知識庫裡面的一些東西，很多發明之後是沒有應用場景的，後來被人發現，這些知識拿來做匿名化很好用。區塊鏈裡面的密碼學技術，能夠很好地實現身份隱匿。大家知道，知乎在技術結構上是實現不了真正意義上的匿名的，區塊鏈可以。

4、規則公開，對所有人公平。入金一塊錢，返利出金十塊錢，所有人都是這個規則，永久不變。你入金一塊錢，先去給前面的人出金，然後後面的人入金，再給你出金。公平吧？這一點，我反思了很多次，覺得還是很公平。

5、可持續迭代。低級的龐氏騙局，首腦、產品設計者、利益分配者、利益獲得者經常是四位一體，而區塊鏈龐氏騙局，可以完全邏輯分離四個角色。實現永續迭代。通過基於社會化的協作，這些項目可以永續迭代下去。圍繞比特幣進行開發，還在不斷更新代碼的資深工程師現在有400名，這些人可以誰也不認識誰，只要這個應用有價值，就可以一直迭代下去。哪個中心化的項目可以做到，就算是BAT級別的公司，也聘不到這么多分散在全球的專業人士。這種社會化迭代方式不受某個具體的人和具體的組織的變動的影響。

「區塊鏈」賦能的龐氏騙局，使用的區塊鏈技術范圍各不相同，因為這個領域的技術還在不斷更新，像智能合約這一塊的應用是這兩年才多起來。最早的區塊鏈應用是比特幣，有人認為比特幣本身就具有龐氏騙局的特徵，2013年我寫過一個回答就隱晦地指出，這種新型的龐氏騙局殺傷力會很大，因為具有無首腦、賬本公開、不會跑路、規則公開公平的特徵。後來，我也發現，身邊的很多人，對龐氏騙局的喜好，遠高於對區塊鏈技術的興趣。一聽說比特幣不是龐氏騙局，在我開始講點區塊鏈的技術之前，一般就默默走開了，反之，你跟他說是龐氏騙局，然後他們接著就會問，在哪裡買？當然，比特幣算不算龐氏騙局是有很多爭議的，因為比特幣的實際應用場景是一直在擴展的。

而在ICO熱潮裡面，有很多空氣幣，則是如假包換的龐氏騙局，是沒有任何應用場景的，這些空氣幣，買的人大概也知道是龐氏騙局，但是看包裝得不錯，就買了。這樣的空氣幣估計有幾百種上千種。涉案范圍遍布全球，金額何止百億。這些ICO使用智能合約進行認籌和分配，然後自行到二級市場流通。這種情況下，出金是沒有保證的，有人虧得血本無歸。很多人區塊鏈專業人士，一直想跟這些應用劃清界線，因為這些空氣幣雖然用了部分區塊鏈的技術，但背後還是一個中心化的組織或者個人，網路節點極少，用戶入金的時候直接匯聚給了某個組織或個人（因此會被卷跑），但無疑，空氣幣還是利用區塊鏈進行入金和發籌，解決了一部分跑路的問題，提升了龐氏騙局的范圍和傳播能力。這是客觀發生的情況。

而從今年開始，隨著技術的進展，利用智能合約實現更加去中心化的龐氏騙局，開始浮出水面。入金和發籌使用智能合約鎖定，完成完整的入金、認籌、出金閉環。已經可以是很純粹的區塊鏈應用，有一些區塊鏈游戲，已經可以很大方地承認，發行後公開聲稱自己就是一個龐氏游戲，他說：你看，規則透明、代碼可見、入金合約鎖定、不會跑路、無人為干預、自動出金。早玩早收益。這是很關鍵的一步突破，公開承認自己是龐氏騙局，這種玩法是以前龐氏騙局1.0和2.0做不到的（不敢公開承認自己是龐氏騙局）。厲害了。玩法簡單粗暴啊。

這就解決了以前龐氏騙局推廣過程的重大障礙，以前是靠洗腦拉人頭，現在靠代碼說話。你看「這段程序不會自己跑路吧，裡面沒有後門吧？首腦已經消失了吧？中本聰被抓住也不影響程序繼續執行吧？」所以區塊鏈龐氏騙局第一批上鉤的是看得懂代碼的碼農，然後這些碼農再站出來說，經技術驗證，確實是這么一個效果，帶動其他不看代碼的人加入。

區塊鏈除了實現娛樂、賭博、詐騙性質的龐氏騙局應用場景之外，在涉及國計民生、公共事業性質的龐氏騙局應用場景也有大展拳腳的機會，甚至可以極大地增強人民獲得感、幸福感，以及實打實改善人民生活。比如基於區塊鏈的國家或全球公共養老金平台應用，這種平台因為基於區塊鏈，可以解決養老金的幾大弊病：

1、資金挪用問題。賬本公開，資金非中心化鎖定，沒有人可以解鎖，除了符合規則的領取人可以出金。沒有挪用可能性。

2、通貨膨脹問題。現行的養老金體制每年都要根據通貨膨脹等一系列復雜的演算法，調整系數，調整完之後，領取者經常會不滿意，因為總額上升了，但是購買力下降了。利用虛擬貨幣無法增發的特性，可以剋制通脹率，保證領取到的都是真金白銀。

3、不可預測的問題。我們很難預測30年後養老金的出金情況，通過智能合約則可以實現提前預測。刺激繳納積極性。

4、政策漏洞和公平問題。任何養老金政策面向的群體多樣化，裡面會有不公平情況，任何人都想著少繳多拿、晚繳早提。區塊鏈的透明度細化到每個賬號，而不是一套籠統的政策，堵住實施過程的漏洞。每個人都是一樣的，多繳多出，早繳早出。甚至可以繼承，永不丟失。

這么干極大地減輕了國家管理養老金的負擔和成本，現有的養老金制度能做到的事情，使用區塊鏈技術之後，仍然能夠做到，比如國家補貼，往合約里打錢就行了，打進去就鎖定，不會有假，比如強制繳納，每筆記錄也都是真實可追查的。總而言之，現有的體制和規則全部可以上鏈，在不影響現有效果的基礎上，提升了效率和產出水平，保證公平，而且因為減少了龐大的管理體系的成本，每個人能領取到的絕對數說不定能上升一大截，這就起到了實打實改善人民生活的效果，還是那句話，有獲得感、幸福感的提升。在養老金這件事情上，我們信任的主體從單一的國家政府，變成國家政府+區塊鏈，50%以上的過程變成固定的軟體程序，我們這樣不是更相信了嗎？如果100%實現鏈上養老金系統，那麼甚至可以打破國家范圍限制，由一段誠實的、不會作弊、無法篡改的代碼來實現，自動入金、自動出金，信任它，就像信任一個死人，不會有錯誤。

下一代人養這一代人的設計，是我們人類進化的一個偉大發明，加速了社會發展的速度，這樣表面看，好像地球上的最後一代人會比較吃虧，其實不會，因為地球的最後一代人也不一定知道自己是最後一代人（可能最後幾秒鍾知道，但又如何），何況地球都消失了，最後一代人還需要出金養老嗎？顯然，不需要啊。

龐氏騙局，最大的弊端就是中途跑路，資金斷裂，區塊鏈在解決這個問題上，有明確的技術解法，而且還能被證明、也能夠被證偽，所以，這個技術是科學的。弊端被消除，好處逐步顯現，龐氏騙局未來還將取得更大的發展。

我也想問一個問題，在人類歷史上，有沒有哪些原來是負面的、或者沒用的東西，後來隨著技術的發展，弊端被消除或規避，作用被發掘，然後變得越來越有用，越來越重要？

⑶ 什麼是區塊鏈共識

所謂「共識機制」，是通過特殊節點的投票，在很短的時間內完成對交易的驗證和確認；對一筆交易，如果利益不相乾的若干個節點能夠達成共識，我們就可以認為全網對此也能夠達成共識。再通俗一點來講，如果中國一名微博大V、美國一名虛擬幣玩家、一名非洲留學生和一名歐洲旅行者互不相識，但他們都一致認為你是個好人，那麼基本上就可以斷定你這人還不壞。
區塊鏈作為一種按時間順序存儲數據的數據結構，可支持不同的共識機制。共識機制是區塊鏈技術的重要組件。區塊鏈共識機制的目標是使所有的誠實節點保存一致的區塊鏈視圖，同時滿足兩個性質：
1）一致性。所有誠實節點保存的區塊鏈的前綴部分完全相同。
2）有效性。由某誠實節點發布的信息終將被其他所有誠實節點記錄在自己的區塊鏈中。

⑷ 成立一家新加坡基金會來做區塊鏈常見的問題有哪些

區塊鏈與基金會之間存在著哪些聯系會遇到哪些問題
很多人在做區塊鏈的時候，通常會注冊一家基金會來與普通公司一起運行，目前選擇新加坡基金會的比較，那麼，注冊一家新加坡基金會來做區塊鏈經常會遇到的問題有哪些呢，下面根據一些客戶關心的問題整理一些分享給大家
1、注冊費用是包含白皮書的費用嗎？
答：沒有的，法律顧問是個性化的業務，費用需要了解項目而定。法律顧問，可以全流程進行服務。包括白皮書的法律條文修改、針對代幣非證券屬性等相關法律法規出具專業法律意見。ico發幣過程中的法律咨詢。

2、關於新加坡基金會的。為什麼要有一家公司來運營，和基金會什麼關系？為什麼不直接注冊一家公司進行ico及對接交易所？
答：基金會本來就是公益組織，公共部門，用基金會做區塊鏈的發行是比較有利於吸引投資和技術開發的，也可通過普通公司直接進行ICO，這個要具體看客戶自己想怎麼操作。
3、ico不就是募集資金的一種方式嗎
答：是的。用已有實際價值的貨幣，參與項目的眾籌，換得項目新發的加密幣。籌款者的好處是得到了開展項目的資金，而參與者則希望項目成功，這樣手中的新發加密幣很可能會升值，從而套利。所謂 ICO，就是投資者使用比特幣等現成的虛擬數字貨幣，去換取ICO項目發行的新代幣。因為新幣種擁有者少、價格波動大，在交易所的賣出價格很可能比發行價高得多。而ICO項目發起方利用融來的傳統數字貨幣，在交易所換回人民幣等法定貨幣，再投入到指定的技術項目中。
4、為什麼不通過常見的渠道來募集資金
答：常見渠道門檻低，沒有監管部門。風險較大。
5、怎麼設立交易所？
答：可根據自身情況自行選擇交易所，一般要選擇有比較強的數字資產安全管理經驗。平台有很多。
6、為什麼要做法律意見書？
根據新加坡金融法和證券法，如果包含有證券性質的虛擬貨幣需要申請特殊金融牌照，所以需要證明該項目不包含有證券性質，那麼就需要律師出具TOKEN非證券化法律意見書，以及證明該項目合法合規的白皮書合規法律意見書，這兩者是大部分客戶都要做的。
7、注冊的新加坡基金會主體在銀行開戶怎麼開？
首先，注冊公眾非盈利基金會是沒有必要開戶的，開了也沒有用，因為基金會本身的性質就是非盈利的，到次年審計的時候無法和金融管理局解釋銀行賬戶上的款項收支呢？第二，銀行對客戶是有挑選的，如果告訴銀行是做區塊鏈的，銀行是不會接受開戶的；第三，無論是私募還是公募，募集來的都是以太坊比特幣這樣的虛擬貨幣，普通銀行賬戶是收不了這些幣種的，所以我這邊不建議到銀行去開戶。

⑸ 什麼是後綴數組 求字元串匹配

後綴數組
在字元串處理當中，後綴樹和後綴數組都是非常有力的工具，其中後綴樹大家了解得比較多，關於後綴數組則很少見於國內的資料。其實後綴數組是後綴樹的一個非常精巧的替代品，它比後綴樹容易編程實現，能夠實現後綴樹的很多功能而時間復雜度也不太遜色，並且，它比後綴樹所佔用的空間小很多。可以說，在信息學競賽中後綴數組比後綴樹要更為實用。因此在本文中筆者想介紹一下後綴數組的基本概念、構造方法，以及配合後綴數組的最長公共前綴數組的構造方法，最後結合一些例子談談後綴數組的應用。
基本概念
首先明確一些必要的定義：
字元集 一個字元集∑是一個建立了全序關系的集合，也就是說，∑中的任意兩個不同的元素α和β都可以比較大小，要麼α<β，要麼β<α（也就是α>β）。字元集∑中的元素稱為字元。
字元串 一個字元串S是將n個字元順次排列形成的數組，n稱為S的長度，表示為len(S)。S的第i個字元表示為S。
子串 字元串S的子串S[i..j]，i≤j，表示S串中從i到j這一段，也就是順次排列S,S[i+1],...,S[j]形成的字元串。
後綴 後綴是指從某個位置i開始到整個串末尾結束的一個特殊子串。字元串S的從i開頭的後綴表示為Suffix(S,i)，也就是Suffix(S,i)=S[i..len(S)]。
關於字元串的大小比較，是指通常所說的「字典順序」比較，也就是對於兩個字元串u、v，令i從1開始順次比較u和v，如果相等則令i加1，否則若u<v則認為u<v，u>v則認為u>v（也就是v<u），比較結束。如果i>len(u)或者i>len(v)仍未比較出結果，那麼若len(u)<len(v)則認為u<v，若len(u)=len(v)則認為u=v，若len(u)>len(v)則u>v。
從字元串的大小比較的定義來看，S的兩個開頭位置不同的後綴u和v進行比較的結果不可能是相等，因為u=v的必要條件len(u)=len(v)在這里不可能滿足。
下面我們約定一個字元集∑和一個字元串S，設len(S)=n，且S[n]='$'，也就是說S以一個特殊字元'$'結尾，並且'$'小於∑中的任何一個字元。除了S[n]之外，S中的其他字元都屬於∑。對於約定的字元串S，從位置i開頭的後綴直接寫成Suffix(i)，省去參數S。
後綴數組 後綴數組SA是一個一維數組，它保存1..n的某個排列SA[1],SA[2],...SA[n]，並且保證 Suffix(SA)<Suffix(SA[i+1]),1≤i<n。也就是將S的n個後綴從小到大進行排序之後把排好序的後綴的開頭位置順次放入SA中。
名次數組 名次數組Rank=SA-1，也就是說若SA=j，則Rank[j]=i，不難看出Rank保存的是Suffix(i)在所有後綴中從小到大排列的「名次」。
構造方法
如何構造後綴數組呢？最直接最簡單的方法當然是把S的後綴都看作一些普通的字元串，按照一般字元串排序的方法對它們從小到大進行排序。
不難看出，這種做法是很笨拙的，因為它沒有利用到各個後綴之間的有機聯系，所以它的效率不可能很高。即使採用字元串排序中比較高效的Multi-key Quick Sort，最壞情況的時間復雜度仍然是O(n2)的，不能滿足我們的需要。
下面介紹倍增演算法(Doubling Algorithm)，它正是充分利用了各個後綴之間的聯系，將構造後綴數組的最壞時間復雜度成功降至O(nlogn)。
對一個字元串u，我們定義u的k-前綴
定義k-前綴比較關系<k、=k和≤k：
設兩個字元串u和v，
u<kv 當且僅當 uk<vk
u=kv 當且僅當 uk=vk
u≤kv 當且僅當 uk≤vk
直觀地看這些加了一個下標k的比較符號的意義就是對兩個字元串的前k個字元進行字典序比較，特別的一點就是在作大於和小於的比較時如果某個字元串的長度不到k也沒有關系，只要能夠在k個字元比較結束之前得到第一個字元串大於或者小於第二個字元串就可以了。
根據前綴比較符的性質我們可以得到以下的非常重要的性質：
性質1.1 對k≥n，Suffix(i)<kSuffix(j) 等價於 Suffix(i)<Suffix(j)。
性質1.2 Suffix(i)=2kSuffix(j)等價於
Suffix(i)=kSuffix(j) 且 Suffix(i+k)=kSuffix(j+k)。
性質1.3 Suffix(i)<2kSuffix(j) 等價於
Suffix(i)<kS(j) 或 (Suffix(i)=kSuffix(j) 且 Suffix(i+k)<kSuffix(j+k))。
這里有一個問題，當i+k>n或者j+k>n的時候Suffix(i+k)或Suffix(j+k)是無明確定義的表達式，但實際上不需要考慮這個問題，因為此時Suffix(i)或者Suffix(j)的長度不超過k，也就是說它們的k-前綴以'$'結尾，於是k-前綴比較的結果不可能相等，也就是說前k個字元已經能夠比出大小，後面的表達式自然可以忽略，這也就看出我們規定S以'$'結尾的特殊用處了。
定義k-後綴數組SAk保存1..n的某個排列SAk[1],SAk[2],…SAk[n]使得Suffix(SAk) ≤kSuffix(SAk[i+1]),1≤i<n。也就是說對所有的後綴在k-前綴比較關系下從小到大排序，並且把排序後的後綴的開頭位置順次放入數組SAk中。
定義k-名次數組Rankk，Rankk代表Suffix(i)在k-前綴關系下從小到大的「名次」，也就是1加上滿足Suffix(j)<kSuffix(i)的j的個數。通過SAk很容易在O(n)的時間內求出Rankk。
假設我們已經求出了SAk和Rankk，那麼我們可以很方便地求出SA2k和Rank2k，因為根據性質1.2和1.3，2k-前綴比較關系可以由常數個k-前綴比較關系組合起來等價地表達，而Rankk數組實際上給出了在常數時間內進行<k和=k比較的方法，即：
Suffix(i)<kSuffix(j) 當且僅當 Rankk<Rankk[j]
Suffix(i)=kSuffix(j) 當且僅當 Rankk=Rankk[j]
因此，比較Suffix(i)和Suffix(j)在k-前綴比較關系下的大小可以在常數時間內完成，於是對所有的後綴在≤k關系下進行排序也就和一般的排序沒有什麼區別了，它實際上就相當於每個Suffix(i)有一個主關鍵字Rankk和一個次關鍵字Rankk[i+k]。如果採用快速排序之類O(nlogn)的排序，那麼從SAk和Rankk構造出SA2k的復雜度就是O(nlogn)。更聰明的方法是採用基數排序，復雜度為O(n)。
求出SA2k之後就可以在O(n)的時間內根據SA2k構造出Rank2k。因此，從SAk和Rankk推出SA2k和Rank2k可以在O(n)時間內完成。
下面只有一個問題需要解決：如何構造出SA1和Rank1。這個問題非常簡單：因為<1，=1和≤1這些運算符實際上就是對字元串的第一個字元進行比較，所以只要把每個後綴按照它的第一個字元進行排序就可以求出SA1，不妨就採用快速排序，復雜度為O(nlogn)。
於是，可以在O(nlogn)的時間內求出SA1和Rank1。
求出了SA1和Rank1，我們可以在O(n)的時間內求出SA2和Rank2，同樣，我們可以再用O(n)的時間求出SA4和Rank4，這樣，我們依次求出：
SA2和Rank2，SA4和Rank4，SA8和Rank8，……直到SAm和Rankm，其中m=2k且m≥n。而根據性質1.1，SAm和SA是等價的。這樣一共需要進行logn次O(n)的過程，因此
可以在O(nlogn)的時間內計算出後綴數組SA和名次數組Rank。
最長公共前綴
現在一個字元串S的後綴數組SA可以在O(nlogn)的時間內計算出來。利用SA我們已經可以做很多事情，比如在O(mlogn)的時間內進行模式匹配，其中m,n分別為模式串和待匹配串的長度。但是要想更充分地發揮後綴數組的威力，我們還需要計算一個輔助的工具——最長公共前綴（Longest Common Prefix）。
對兩個字元串u,v定義函數lcp(u,v)=max{i|u=iv}，也就是從頭開始順次比較u和v的對應字元，對應字元持續相等的最大位置，稱為這兩個字元串的最長公共前綴。
對正整數i,j定義LCP(i,j)=lcp(Suffix(SA),Suffix(SA[j])，其中i,j均為1至n的整數。LCP(i,j)也就是後綴數組中第i個和第j個後綴的最長公共前綴的長度。
關於LCP有兩個顯而易見的性質：
性質2.1 LCP(i,j)=LCP(j,i)
性質2.2 LCP(i,i)=len(Suffix(SA))=n-SA+1
這兩個性質的用處在於，我們計算LCP(i,j)時只需要考慮i<j的情況，因為i>j時可交換i,j，i=j時可以直接輸出結果n-SA+1。
直接根據定義，用順次比較對應字元的方法來計算LCP(i,j)顯然是很低效的，時間復雜度為O(n)，所以我們必須進行適當的預處理以降低每次計算LCP的復雜度。
經過仔細分析，我們發現LCP函數有一個非常好的性質：
設i<j，則LCP(i,j)=min{LCP(k-1,k)|i+1≤k≤j} （LCP Theorem）
要證明LCP Theorem，首先證明LCP Lemma:
對任意1≤i<j<k≤n，LCP(i,k)=min{LCP(i,j),LCP(j,k)}
證明：設p=min{LCP(i,j),LCP(j,k)}，則有LCP(i,j)≥p,LCP(j,k)≥p。
設Suffix(SA)=u,Suffix(SA[j])=v,Suffix(SA[k])=w。
由u=LCP(i,j)v得u=pv；同理v=pw。
於是Suffix(SA)=pSuffix(SA[k])，即LCP(i,k)≥p。 (1)
又設LCP(i,k)=q>p，則
u[1]=w[1],u[2]=w[2],...u[q]=w[q]。
而min{LCP(i,j),LCP(j,k)}=p說明u[p+1]≠v[p+1]或v[p+1]≠w[q+1]，
設u[p+1]=x,v[p+1]=y,w[p+1]=z，顯然有x≤y≤z，又由p<q得p+1≤q，應該有x=z，也就是x=y=z，這與u[p+1]≠v[p+1]或v[p+1]≠w[q+1]矛盾。
於是，q>p不成立，即LCP(i,k)≤p。 (2)
綜合(1),(2)知 LCP(i,k)=p=min{LCP(i,j),LCP(j,k)}，LCP Lemma得證。
於是LCP Theorem可以證明如下：
當j-i=1和j-i=2時，顯然成立。
設j-i=m時LCP Theorem成立，當j-i=m+1時，
由LCP Lemma知LCP(i,j)=min{LCP(i,i+1),LCP(i+1,j)}，
因j-(i+1)≤m，LCP(i+1,j)=min{LCP(k-1,k)|i+2≤k≤j}，故當j-i=m+1時，仍有
LCP(i,j)=min{LCP(i,i+1),min{LCP(k-1,k)|i+2≤k≤j}}=min{LCP(k-1,k}|i+1≤k≤j)
根據數學歸納法，LCP Theorem成立。
根據LCP Theorem得出必然的一個推論：
LCP Corollary 對i≤j<k，LCP(j,k)≥LCP(i,k)。
定義一維數組height，令height=LCP(i-1,i)，1<i≤n，並設height[1]=0。
由LCP Theorem，LCP(i,j)=min{height[k]|i+1≤k≤j}，也就是說，計算LCP(i,j)等同於詢問一維數組height中下標在i+1到j范圍內的所有元素的最小值。如果height數組是固定的，這就是非常經典的RMQ（Range Minimum Query）問題。
RMQ問題可以用線段樹或靜態排序樹在O(nlogn)時間內進行預處理，之後每次詢問花費時間O(logn)，更好的方法是RMQ標准演算法，可以在O(n)時間內進行預處理，每次詢問可以在常數時間內完成。
對於一個固定的字元串S，其height數組顯然是固定的，只要我們能高效地求出height數組，那麼運用RMQ方法進行預處理之後，每次計算LCP(i,j)的時間復雜度就是常數級了。於是只有一個問題——如何盡量高效地算出height數組。
根據計算後綴數組的經驗，我們不應該把n個後綴看作互不相關的普通字元串，而應該盡量利用它們之間的聯系，下面證明一個非常有用的性質：
為了描述方便，設h=height[Rank]，即height=h[SA]。h數組滿足一個性質：
性質3 對於i>1且Rank>1，一定有h≥h[i-1]-1。
為了證明性質3，我們有必要明確兩個事實：
設i<n,j<n，Suffix(i)和Suffix(j)滿足lcp(Suffix(i),Suffix(j)>1，則成立以下兩點：
Fact 1 Suffix(i)<Suffix(j) 等價於 Suffix(i+1)<Suffix(j+1)。
Fact 2 一定有lcp(Suffix(i+1),Suffix(j+1))=lcp(Suffix(i),Suffix(j))-1。
看起來很神奇，但其實很自然：lcp(Suffix(i),Suffix(j))>1說明Suffix(i)和Suffix(j)的第一個字元是相同的，設它為α，則Suffix(i)相當於α後連接Suffix(i+1)，Suffix(j)相當於α後連接Suffix(j+1)。比較Suffix(i)和Suffix(j)時，第一個字元α是一定相等的，於是後面就等價於比較Suffix(i)和Suffix(j)，因此Fact 1成立。Fact 2可類似證明。
於是可以證明性質3：
當h[i-1]≤1時，結論顯然成立，因h≥0≥h[i-1]-1。
當h[i-1]>1時，也即height[Rank[i-1]]>1，可見Rank[i-1]>1，因height[1]=0。
令j=i-1,k=SA[Rank[j]-1]。顯然有Suffix(k)<Suffix(j)。
根據h[i-1]=lcp(Suffix(k),Suffix(j))>1和Suffix(k)<Suffix(j)：
由Fact 2知lcp(Suffix(k+1),Suffix(i))=h[i-1]-1。
由Fact 1知Rank[k+1]<Rank，也就是Rank[k+1]≤Rank-1。
於是根據LCP Corollary，有
LCP(Rank-1,Rank)≥LCP(Rank[k+1],Rank)
=lcp(Suffix(k+1),Suffix(i))
=h[i-1]-1
由於h=height[Rank]=LCP(Rank-1,Rank)，最終得到 h≥h[i-1]-1。
根據性質3，可以令i從1循環到n按照如下方法依次算出h：
若Rank=1，則h=0。字元比較次數為0。
若i=1或者h[i-1]≤1，則直接將Suffix(i)和Suffix(Rank-1)從第一個字元開始依次比較直到有字元不相同，由此計算出h。字元比較次數為h+1，不超過h-h[i-1]+2。
否則，說明i>1，Rank>1，h[i-1]>1，根據性質3，Suffix(i)和Suffix(Rank-1)至少有前h[i-1]-1個字元是相同的，於是字元比較可以從h[i-1]開始，直到某個字元不相同，由此計算出h。字元比較次數為h-h[i-1]+2。
設SA[1]=p，那麼不難看出總的字元比較次數不超過
也就是說，整個演算法的復雜度為O(n)。
求出了h數組，根據關系式height=h[SA]可以在O(n)時間內求出height數組，於是
可以在O(n)時間內求出height數組。
結合RMQ方法，在O(n)時間和空間進行預處理之後就能做到在常數時間內計算出對任意(i,j)計算出LCP(i,j)。
因為lcp(Suffix(i),Suffix(j))=LCP(Rank,Rank[j])，所以我們也就可以在常數時間內求出S的任何兩個後綴之間的最長公共前綴。這正是後綴數組能強有力地處理很多字元串問題的重要原因之一。

⑹ 後綴數組的height數組有什麼性質

（1）height 數組：定義height[i]=suffix(SA[i-1])和suffix(SA[i])的最長公共前綴，也就是排名相鄰的兩個後綴的最長公共前綴的長度 。
（2）h[i]=height[rank[i]]，也就是suffix(i)和排序後在它前一名的後綴的最長公共前綴的長度。
（3）函數lcp(u,v)=max{i|u=v}，也就是從頭開始順次比較u和v的對應字元，對應字元持續相等的最大位置，稱為這兩個字元串u,v的最長公共前綴的長度。
（4）LCP(i,j)：對正整數i,j 定義LCP(i,j)=lcp(Suffix(SA[i]),Suffix(SA[j])，其中i,j 均為1至n的整數。LCP(i,j)也就是後綴數組中第i個和第j個後綴的最長公共前綴的長度。

⑺ 區塊鏈發幣一定要注冊基金會嗎有什麼要求

區塊鏈，是由一組技術實現的大規模、去中心化的經濟組織模式。區塊鏈引起廣泛關注在於它改變了許多領域的原有經濟組織模式。人們現在探索區塊鏈在經濟各領域的應用，本質上也是在尋找利用區塊鏈調整或創新原有的企業、產業、區域的經濟組織方式，尋找降低成本、提高收益的新途徑。將區塊鏈作為一種經濟組織模式，向下可以延伸到它的實現技術，向上可以拓展到對社會組織和社會意識的影響，更容易理解區塊鏈帶來的復雜社會影響。
現在國內已經禁止發幣了，但是海外政策寬松，不過做區塊鏈技術的公司都會要求發幣方有主體公司作為依託，才會去合作。所以大多數做區塊鏈行業的都有注冊一個主體的基金會。
英國、美國、開曼、新加坡、甚至馬爾他都可以注冊基金會，那麼這些地區有哪些區別呢？英美現在主要是做非盈利性基金會，類似於國內的社會團體，單純募zi避稅是沒有問題的，但是發幣做法律合規是做不了的；開曼基金會又叫做有限合夥（ELP），是一個普通合夥人（GP）和一個或多個有限合夥人（LP）組成，這樣的組合成本上勢必會增加，目前就是阿里、京東、網路等一些大集團為了上市所選擇的；至於馬爾他，政策及其不穩定，而且連收款都受中國制裁，所以大多數人都是「望而卻步」。
所以現在新加坡還是區塊鏈落戶的中心地區，這主要得益於新加坡寬松的經濟環境和良好的政策，在新加坡注冊基金會，第一離中國近，有什麼消息可以及時把控；第二新加坡非盈利性質基金會是免稅的；第三大眾的選擇，許多知名的代幣發行都選擇先注冊新加坡基金會；第四發行代幣需要做法律合規，這一塊新加坡有非常完善的服務體系。
注冊新加坡基金會所需要的資料：
1、2名注冊人身份證（掃描件），在新加坡無犯罪記錄，年滿十八周歲即可。
2、公司名稱：以LTD.結尾，可以加FUND/FOUNDATION。
3、注冊資本：1新幣，政府規定。
4、公司性質：公眾擔保（非盈利）。
5、注冊時間：10-25個工作日。

⑻ 國家集訓隊論文

後綴數組

【作者】
安徽省蕪湖市第一中學 許智磊

【摘要】
本文介紹後綴數組的基本概念、方法以及應用。
首先介紹O(nlogn)復雜度構造後綴數組的倍增演算法，接著介紹了配合後綴數組的最長公共前綴 LCP（Longest Common Prefix）的計算方法，並給出一個線性時間內計算height數組（記錄跨度為1的LCP值的數組）的演算法。最後介紹兩個應用後綴數組的例子：多模式串的模式匹配以及求最長迴文子串。

【關鍵字】
字元串 後綴 k-前綴比較關系
後綴數組 名次數組 後綴樹 倍增演算法 基數排序
最長公共前綴 RMQ問題 模式匹配 迴文串 最長迴文子串

【正文】
在字元串處理當中，後綴樹和後綴數組都是非常有力的工具，其中後綴樹大家了解得比較多，關於後綴數組則很少見於國內的資料。其實後綴數組是後綴樹的一個非常精巧的替代品，它比後綴樹容易編程實現，能夠實現後綴樹的很多功能而時間復雜度也不太遜色，並且，它比後綴樹所佔用的空間小很多。可以說，在信息學競賽中後綴數組比後綴樹要更為實用。因此在本文中筆者想介紹一下後綴數組的基本概念、構造方法，以及配合後綴數組的最長公共前綴數組的構造方法，最後結合一些例子談談後綴數組的應用。

基本概念

首先明確一些必要的定義：

字元集 一個字元集∑是一個建立了全序關系的集合，也就是說，∑中的任意兩個不同的元素α和β都可以比較大小，要麼α<β，要麼β<α（也就是α>β）。字元集∑中的元素稱為字元。
字元串 一個字元串S是將n個字元順次排列形成的數組，n稱為S的長度，表示為len(S)。S的第i個字元表示為S[i]。
子串 字元串S的子串S[i..j]，i≤j，表示S串中從i到j這一段，也就是順次排列S[i],S[i+1],...,S[j]形成的字元串。
後綴 後綴是指從某個位置i開始到整個串末尾結束的一個特殊子串。字元串S的從i開頭的後綴表示為Suffix(S,i)，也就是Suffix(S,i)=S[i..len(S)]。

關於字元串的大小比較，是指通常所說的「字典順序」比較，也就是對於兩個字元串u、v，令i從1開始順次比較u[i]和v[i]，如果相等則令i加1，否則若u[i]<v[i]則認為u<v，u[i]>v[i]則認為u>v（也就是v<u），比較結束。如果i>len(u)或者i>len(v)仍比較出結果，那麼若len(u)<len(v)則認為u<v，若len(u)=len(v)則認為u=v，若len(u)>len(v)則u>v。
從字元串的大小比較的定義來看，S的兩個開頭位置不同的後綴u和v進行比較的結果不可能是相等，因為u=v的必要條件len(u)=len(v)在這里不可能滿足。

下面我們約定一個字元集∑和一個字元串S，設len(S)=n，且S[n]='$'，也就是說S以一個特殊字元'$'結尾，並且'$'小於∑中的任何一個字元。除了S[n]之外，S中的其他字元都屬於∑。對於約定的字元串S，從位置i開頭的後綴直接寫成Suffix(i)，省去參數S。

後綴數組 後綴數組SA是一個一維數組，它保存1..n的某個排列SA[1],SA[2],...SA[n]，並且保證 Suffix(SA[i])<Suffix(SA[i+1]),1≤i<n。也就是將S的n個後綴從小到大進行排序之後把排好序的後綴的開頭位置順次放入SA中。
名次數組 名次數組Rank=SA-1，也就是說若SA[i]=j，則Rank[j]=i，不難看出Rank[i]保存的是Suffix(i)在所有後綴中從小到大排列的「名次」。

構造方法
如何構造後綴數組呢？最直接最簡單的方法當然是把S的後綴都看作一些普通的字元串，按照一般字元串排序的方法對它們從小到大進行排序。
不難看出，這種做法是很笨拙的，因為它沒有利用到各個後綴之間的有機聯系，所以它的效率不可能很高。即使採用字元串排序中比較高效的Multi-key Quick Sort，最壞情況的時間復雜度仍然是O(n2)的，不能滿足我們的需要。
下面介紹倍增演算法(Doubling Algorithm)，它正是充分利用了各個後綴之間的聯系，將構造後綴數組的最壞時間復雜度成功降至O(nlogn)。

對一個字元串u，我們定義u的k-前綴

定義k-前綴比較關系<k、=k和≤k：
設兩個字元串u和v，
u<kv 當且僅當 uk<vk
u=kv 當且僅當 uk=vk
u≤kv 當且僅當 uk≤vk

直觀地看這些加了一個下標k的比較符號的意義就是對兩個字元串的前k個字元進行字典序比較，特別的一點就是在作大於和小於的比較時如果某個字元串的長度不到k也沒有關系，只要能夠在k個字元比較結束之前得到第一個字元串大於或者小於第二個字元串就可以了。
根據前綴比較符的性質我們可以得到以下的非常重要的性質：
性質1.1 對k≥n，Suffix(i)<kSuffix(j) 等價於 Suffix(i)<Suffix(j)。
性質1.2 Suffix(i)=2kSuffix(j)等價於
Suffix(i)=kSuffix(j) 且 Suffix(i+k)=kSuffix(j+k)。
性質1.3 Suffix(i)<2kSuffix(j) 等價於
Suffix(i)<kS(j) 或 (Suffix(i)=kSuffix(j) 且 Suffix(i+k)<kSuffix(j+k))。
這里有一個問題，當i+k>n或者j+k>n的時候Suffix(i+k)或Suffix(j+k)是無明確定義的表達式，但實際上不需要考慮這個問題，因為此時Suffix(i)或者Suffix(j)的長度不超過k，也就是說它們的k-前綴以'$'結尾，於是k-前綴比較的結果不可能相等，也就是說前k個字元已經能夠比出大小，後面的表達式自然可以忽略，這也就看出我們規定S以'$'結尾的特殊用處了。

定義k-後綴數組SAk保存1..n的某個排列SAk[1],SAk[2],…SAk[n]使得Suffix(SAk[i]) ≤kSuffix(SAk[i+1]),1≤i<n。也就是說對所有的後綴在k-前綴比較關系下從小到大排序，並且把排序後的後綴的開頭位置順次放入數組SAk中。
定義k-名次數組Rankk，Rankk[i]代表Suffix(i)在k-前綴關系下從小到大的「名次」，也就是1加上滿足Suffix(j)<kSuffix(i)的j的個數。通過SAk很容易在O(n)的時間內求出Rankk。
假設我們已經求出了SAk和Rankk，那麼我們可以很方便地求出SA2k和Rank2k，因為根據性質1.2和1.3，2k-前綴比較關系可以由常數個k-前綴比較關系組合起來等價地表達，而Rankk數組實際上給出了在常數時間內進行<k和=k比較的方法，即：
Suffix(i)<kSuffix(j) 當且僅當 Rankk[i]<Rankk[j]
Suffix(i)=kSuffix(j) 當且僅當 Rankk[i]=Rankk[j]
因此，比較Suffix(i)和Suffix(j)在k-前綴比較關系下的大小可以在常數時間內完成，於是對所有的後綴在≤k關系下進行排序也就和一般的排序沒有什麼區別了，它實際上就相當於每個Suffix(i)有一個主關鍵字Rankk[i]和一個次關鍵字Rankk[i+k]。如果採用快速排序之類O(nlogn)的排序，那麼從SAk和Rankk構造出SA2k的復雜度就是O(nlogn)。更聰明的方法是採用基數排序，復雜度為O(n)。
求出SA2k之後就可以在O(n)的時間內根據SA2k構造出Rank2k。因此，從SAk和Rankk推出SA2k和Rank2k可以在O(n)時間內完成。
下面只有一個問題需要解決：如何構造出SA1和Rank1。這個問題非常簡單：因為<1，=1和≤1這些運算符實際上就是對字元串的第一個字元進行比較，所以只要把每個後綴按照它的第一個字元進行排序就可以求出SA1，不妨就採用快速排序，復雜度為O(nlogn)。
於是，可以在O(nlogn)的時間內求出SA1和Rank1。
求出了SA1和Rank1，我們可以在O(n)的時間內求出SA2和Rank2，同樣，我們可以再用O(n)的時間求出SA4和Rank4，這樣，我們依次求出：
SA2和Rank2，SA4和Rank4，SA8和Rank8，……直到SAm和Rankm，其中m=2k且m≥n。而根據性質1.1，SAm和SA是等價的。這樣一共需要進行logn次O(n)的過程，因此
可以在O(nlogn)的時間內計算出後綴數組SA和名次數組Rank。

最長公共前綴
現在一個字元串S的後綴數組SA可以在O(nlogn)的時間內計算出來。利用SA我們已經可以做很多事情，比如在O(mlogn)的時間內進行模式匹配，其中m,n分別為模式串和待匹配串的長度。但是要想更充分地發揮後綴數組的威力，我們還需要計算一個輔助的工具——最長公共前綴（Longest Common Prefix）。
對兩個字元串u,v定義函數lcp(u,v)=max{i|u=iv}，也就是從頭開始順次比較u和v的對應字元，對應字元持續相等的最大位置，稱為這兩個字元串的最長公共前綴。
對正整數i,j定義LCP(i,j)=lcp(Suffix(SA[i]),Suffix(SA[j])，其中i,j均為1至n的整數。LCP(i,j)也就是後綴數組中第i個和第j個後綴的最長公共前綴的長度。
關於LCP有兩個顯而易見的性質：
性質2.1 LCP(i,j)=LCP(j,i)
性質2.2 LCP(i,i)=len(Suffix(SA[i]))=n-SA[i]+1
這兩個性質的用處在於，我們計算LCP(i,j)時只需要考慮i<j的情況，因為i>j時可交換i,j，i=j時可以直接輸出結果n-SA[i]+1。

直接根據定義，用順次比較對應字元的方法來計算LCP(i,j)顯然是很低效的，時間復雜度為O(n)，所以我們必須進行適當的預處理以降低每次計算LCP的復雜度。
經過仔細分析，我們發現LCP函數有一個非常好的性質：
設i<j，則LCP(i,j)=min{LCP(k-1,k)|i+1≤k≤j} （LCP Theorem）

要證明LCP Theorem，首先證明LCP Lemma:
對任意1≤i<j<k≤n，LCP(i,k)=min{LCP(i,j),LCP(j,k)}
證明：設p=min{LCP(i,j),LCP(j,k)}，則有LCP(i,j)≥p,LCP(j,k)≥p。
設Suffix(SA[i])=u,Suffix(SA[j])=v,Suffix(SA[k])=w。
由u=LCP(i,j)v得u=pv；同理v=pw。
於是Suffix(SA[i])=pSuffix(SA[k])，即LCP(i,k)≥p。 (1)

又設LCP(i,k)=q>p，則
u[1]=w[1],u[2]=w[2],...u[q]=w[q]。
而min{LCP(i,j),LCP(j,k)}=p說明u[p+1]≠v[p+1]或v[p+1]≠w[q+1]，
設u[p+1]=x,v[p+1]=y,w[p+1]=z，顯然有x≤y≤z，又由p<q得p+1≤q，應該有x=z，也就是x=y=z，這與u[p+1]≠v[p+1]或v[p+1]≠w[q+1]矛盾。
於是，q>p不成立，即LCP(i,k)≤p。 (2)
綜合(1),(2)知 LCP(i,k)=p=min{LCP(i,j),LCP(j,k)}，LCP Lemma得證。

於是LCP Theorem可以證明如下：
當j-i=1和j-i=2時，顯然成立。
設j-i=m時LCP Theorem成立，當j-i=m+1時，
由LCP Lemma知LCP(i,j)=min{LCP(i,i+1),LCP(i+1,j)}，
因j-(i+1)≤m，LCP(i+1,j)=min{LCP(k-1,k)|i+2≤k≤j}，故當j-i=m+1時，仍有
LCP(i,j)=min{LCP(i,i+1),min{LCP(k-1,k)|i+2≤k≤j}}=min{LCP(k-1,k}|i+1≤k≤j)
根據數學歸納法，LCP Theorem成立。

根據LCP Theorem得出必然的一個推論：
LCP Corollary 對i≤j<k，LCP(j,k)≥LCP(i,k)。

定義一維數組height，令height[i]=LCP(i-1,i)，1<i≤n，並設height[1]=0。
由LCP Theorem，LCP(i,j)=min{height[k]|i+1≤k≤j}，也就是說，計算LCP(i,j)等同於詢問一維數組height中下標在i+1到j范圍內的所有元素的最小值。如果height數組是固定的，這就是非常經典的RMQ（Range Minimum Query）問題。
RMQ問題可以用線段樹或靜態排序樹在O(nlogn)時間內進行預處理，之後每次詢問花費時間O(logn)，更好的方法是RMQ標准演算法，可以在O(n)時間內進行預處理，每次詢問可以在常數時間內完成。
對於一個固定的字元串S，其height數組顯然是固定的，只要我們能高效地求出height數組，那麼運用RMQ方法進行預處理之後，每次計算LCP(i,j)的時間復雜度就是常數級了。於是只有一個問題——如何盡量高效地算出height數組。
根據計算後綴數組的經驗，我們不應該把n個後綴看作互不相關的普通字元串，而應該盡量利用它們之間的聯系，下面證明一個非常有用的性質：
為了描述方便，設h[i]=height[Rank[i]]，即height[i]=h[SA[i]]。h數組滿足一個性質：
性質3 對於i>1且Rank[i]>1，一定有h[i]≥h[i-1]-1。
為了證明性質3，我們有必要明確兩個事實：

設i<n,j<n，Suffix(i)和Suffix(j)滿足lcp(Suffix(i),Suffix(j)>1，則成立以下兩點：
Fact 1 Suffix(i)<Suffix(j) 等價於 Suffix(i+1)<Suffix(j+1)。
Fact 2 一定有lcp(Suffix(i+1),Suffix(j+1))=lcp(Suffix(i),Suffix(j))-1。
看起來很神奇，但其實很自然：lcp(Suffix(i),Suffix(j))>1說明Suffix(i)和Suffix(j)的第一個字元是相同的，設它為α，則Suffix(i)相當於α後連接Suffix(i+1)，Suffix(j)相當於α後連接Suffix(j+1)。比較Suffix(i)和Suffix(j)時，第一個字元α是一定相等的，於是後面就等價於比較Suffix(i)和Suffix(j)，因此Fact 1成立。Fact 2可類似證明。

於是可以證明性質3：
當h[i-1]≤1時，結論顯然成立，因h[i]≥0≥h[i-1]-1。
當h[i-1]>1時，也即height[Rank[i-1]]>1，可見Rank[i-1]>1，因height[1]=0。
令j=i-1,k=SA[Rank[j]-1]。顯然有Suffix(k)<Suffix(j)。
根據h[i-1]=lcp(Suffix(k),Suffix(j))>1和Suffix(k)<Suffix(j)：
由Fact 2知lcp(Suffix(k+1),Suffix(i))=h[i-1]-1。
由Fact 1知Rank[k+1]<Rank[i]，也就是Rank[k+1]≤Rank[i]-1。
於是根據LCP Corollary，有
LCP(Rank[i]-1,Rank[i])≥LCP(Rank[k+1],Rank[i])
=lcp(Suffix(k+1),Suffix(i))
=h[i-1]-1
由於h[i]=height[Rank[i]]=LCP(Rank[i]-1,Rank[i])，最終得到 h[i]≥h[i-1]-1。

根據性質3，可以令i從1循環到n按照如下方法依次算出h[i]：
若Rank[i]=1，則h[i]=0。字元比較次數為0。
若i=1或者h[i-1]≤1，則直接將Suffix(i)和Suffix(Rank[i]-1)從第一個字元開始依次比較直到有字元不相同，由此計算出h[i]。字元比較次數為h[i]+1，不超過h[i]-h[i-1]+2。
否則，說明i>1，Rank[i]>1，h[i-1]>1，根據性質3，Suffix(i)和Suffix(Rank[i]-1)至少有前h[i-1]-1個字元是相同的，於是字元比較可以從h[i-1]開始，直到某個字元不相同，由此計算出h[i]。字元比較次數為h[i]-h[i-1]+2。

設SA[1]=p，那麼不難看出總的字元比較次數不超過

也就是說，整個演算法的復雜度為O(n)。
求出了h數組，根據關系式height[i]=h[SA[i]]可以在O(n)時間內求出height數組，於是
可以在O(n)時間內求出height數組。

結合RMQ方法，在O(n)時間和空間進行預處理之後就能做到在常數時間內計算出對任意(i,j)計算出LCP(i,j)。
因為lcp(Suffix(i),Suffix(j))=LCP(Rank[i],Rank[j])，所以我們也就可以在常數時間內求出S的任何兩個後綴之間的最長公共前綴。這正是後綴數組能強有力地處理很多字元串問題的重要原因之一。

後綴數組的應用
下面結合兩個例子談談如何運用後綴數組。

例一 多模式串的模式匹配問題

後綴數組與後綴樹的比較