Ukkonen's suffix tree algorithm in plain English原文地址(最高票答案)
下文將嘗試描述Ukkonen算法，我們首先會(huì)展示在字符串比較簡(jiǎn)單的情況下（即：字符串中沒有重復(fù)字符時(shí)）Ukkonen算法會(huì)做些什么，然后擴(kuò)展到完整的算法。
首先，一點(diǎn)初步的陳述。
我們正在構(gòu)造的數(shù)據(jù)結(jié)構(gòu)，跟搜索Trie有點(diǎn)類似，所以它將會(huì)有一個(gè)根節(jié)點(diǎn)，有邊從根節(jié)點(diǎn)出發(fā)，指向根節(jié)點(diǎn)的子節(jié)點(diǎn)，然后也有邊從這些子節(jié)點(diǎn)出發(fā)指向這些根節(jié)點(diǎn)子節(jié)點(diǎn)的子節(jié)點(diǎn)，如此一層層的下去直到葉節(jié)點(diǎn)。
但是：根搜索Trie不同的是，這里不再使用單個(gè)的字符來標(biāo)記一條邊，而是使用一對(duì)整數(shù)[from, to].它們是指向文本的指針。在這樣的一個(gè)場(chǎng)景下，一條邊攜帶了一個(gè)任意長(zhǎng)度的字符串，但是只使用了O(1) 的空間（兩根指針）。
基本原理
我將先展示如何給一個(gè)特別簡(jiǎn)單的字符串構(gòu)造后綴樹，一個(gè)沒有重復(fù)字符的字符串：
abc
該算法從左到右一步一步的運(yùn)行工作。字符串中的每一個(gè)字符都有一個(gè)步驟。每一個(gè)步驟可能涉及到多個(gè)單獨(dú)的操作，但是我們會(huì)看到（最終觀察結(jié)果）操作總數(shù)為O（n）。
所以，我們從左側(cè)開始，并且首先通過創(chuàng)建一條從根節(jié)點(diǎn)root(在左邊)到一個(gè)葉節(jié)點(diǎn)的邊插入一個(gè)單獨(dú)的字符a，并且將這條邊標(biāo)記為[0, #]. [0, #]這個(gè)標(biāo)記所表達(dá)的意思是這條邊被用來表示當(dāng)前字符串從0位置開始到當(dāng)前位置結(jié)束的子串。其中#表示的就是當(dāng)前位置。在這一步，當(dāng)前位置是1(即a的后面)。
所以我們有了一顆初始狀態(tài)的樹，它看起來長(zhǎng)這樣：
而它的意義是這樣的：
現(xiàn)在我們前進(jìn)到位置2（b的后面）。我們?cè)谒惴ǖ拿恳徊降哪繕?biāo)是：將到當(dāng)前位置為止的所有后綴都插入到后綴樹中。我們通過一下方式達(dá)到這一目的：
將當(dāng)前a邊擴(kuò)展成為ab。
為后綴b插入一條新的邊。
在我們當(dāng)前的表示中看起來像這樣：
它的意義是這樣的：
我們觀察到兩件事：
現(xiàn)在表示ab的邊跟它之前在初始樹中的表示是一樣的：[0, #]。 它所表達(dá)的意思被自動(dòng)更新了因?yàn)槲覀儗?的值從1更新到了2 。
每一條邊占用的空間都是固定的，因?yàn)樗鼈冎话瑑蓚€(gè)指向文本的指針，不論它們所表示的子串有多長(zhǎng)。
接下來我們?cè)俅胃庐?dāng)前位置，更新我們的樹結(jié)構(gòu)，給每一條已存在的邊連接字符串c并且為新的后綴c插入一條新的邊。
在我們的表示中看起來是這樣的：
而它的意義是這樣的：
我們可以觀察到：
在每一個(gè)步驟完成的時(shí)候，我們的樹都是正確包含所有后綴的的后綴樹。
文本中有多少個(gè)字符串，就有多少個(gè)步驟。
在每一步中我們所要進(jìn)行的步驟數(shù)量都是固定的，因?yàn)槊恳粋€(gè)已經(jīng)存在的節(jié)點(diǎn)所表示的后綴都在#的值增加的時(shí)候被自動(dòng)更新了，并且為最后的單字符后綴插入一條新邊可以在O(1)的時(shí)間復(fù)雜度內(nèi)完成。因此對(duì)于一個(gè)長(zhǎng)度為n的字符串，我們只需要花費(fèi)O(n)的時(shí)間。
第一次擴(kuò)展：簡(jiǎn)單的重復(fù)
當(dāng)然這個(gè)簡(jiǎn)化版的算法能夠如此完美的運(yùn)行僅僅是因?yàn)槲覀兊淖址话魏沃貜?fù)字符，我們現(xiàn)在來看一個(gè)更真實(shí)的字符串：
abcabxabcd
這個(gè)字符串以前例中abc為開頭，然后ab重復(fù)出現(xiàn)，后面跟隨不重復(fù)的x, 然后abc重復(fù)出現(xiàn)，最后以d結(jié)尾。
步驟1到3: 在進(jìn)行了前面三步之后我們從前例中獲得了這樣的一顆后綴樹：
步驟4: 我們將#移動(dòng)到位置4，這將會(huì)把所有已經(jīng)存在的節(jié)點(diǎn)隱式的更新成這樣：
然后我們需要在根節(jié)點(diǎn)處插入當(dāng)前節(jié)點(diǎn)的最后一個(gè)后綴a。
在此之前，我們先介紹兩個(gè)新的變量（除#外的），它們當(dāng)然一直都在我們的程序上下文中但是直到現(xiàn)在我們還沒有用過它們：
active point, 這是一個(gè)三元組 (active_node, active_edge, active_length).
remainder, 一個(gè)用來表示我們還剩下多少個(gè)后綴需要插入的整數(shù)。
這兩個(gè)變量的含義將會(huì)很快的變得清晰起來，但是現(xiàn)在我們僅需要了解：
在這個(gè)簡(jiǎn)單的abc示例里面，active point一直都是(root, null, 0), 即：active_node一直都是根節(jié)點(diǎn)，active_edge一直都是null, active_length一直都是0。這樣造成的影響是我們每一步中我們插入的新邊都是直接插在根節(jié)點(diǎn)上的新邊。我們將會(huì)很快看到為什么我們需要這樣的一個(gè)元組來表示這個(gè)信息。
在每一步開始之前remainder都總是被設(shè)置成1。這代表我們?cè)诿恳徊街行枰迦氲暮缶Y數(shù)量都是1（總是最后那個(gè)字符）。
現(xiàn)在情況開始不一樣了。當(dāng)我們嘗試將現(xiàn)在需要插入的最后那個(gè)字符a插入到根節(jié)點(diǎn)的時(shí)候，我們會(huì)發(fā)現(xiàn)現(xiàn)在已經(jīng)有一條從節(jié)點(diǎn)出來的以a開頭的邊，具體來說：abca這條邊。當(dāng)遇到這種情況的時(shí)候我們這樣做：
我們不在根節(jié)點(diǎn)插入新邊[4,#]。相反，我們發(fā)現(xiàn)后綴a已經(jīng)在樹里面了。它在一條更長(zhǎng)的邊的中間結(jié)束，但我們不去管它，直接讓它保持它現(xiàn)在的樣子就行了。
我們將active point的值更新為(root, ‘a(chǎn)’, 1) 。這代表我們現(xiàn)在的活動(dòng)點(diǎn)更新為了從根節(jié)點(diǎn)出發(fā)的一個(gè)以a開頭的邊的某處。根據(jù)active_length, 我們知道是在這條邊開始的一個(gè)位置之后。我們發(fā)現(xiàn)具體的邊是由其首個(gè)字符指定的。這樣就足夠了因?yàn)樵谀硞€(gè)節(jié)點(diǎn)處以某一個(gè)特定字符開始的邊只可能有一條(通過完整的閱讀本文你會(huì)發(fā)現(xiàn)這是正確的)。
我們還會(huì)將remainder的值增加一，所以在下一個(gè)步驟開始的時(shí)候remainder的值將會(huì)為2 。
觀察：當(dāng)我們需要插入的最后那個(gè)后綴已經(jīng)出現(xiàn)在樹里面的時(shí)候，樹本身并沒有被改變(我們只更新active point和remainder)。現(xiàn)在這棵樹已經(jīng)不再是到當(dāng)前位置為止的后綴樹的準(zhǔn)確表示了，但是它的確包含了所有的后綴(因?yàn)樽詈笮枰迦氲哪莻€(gè)后綴a已經(jīng)被隱式包含了)。因此，除了更新我們的變量之外（所有的這些變量都是固定長(zhǎng)度的，時(shí)間復(fù)雜度是O(1)）， 我們?cè)谶@一步?jīng)]有做其他任何事情。
步驟5: 我們把代表當(dāng)前位置的#更新為5，這將會(huì)自動(dòng)把樹結(jié)構(gòu)更新為這樣：
并且因?yàn)閞emainder是2，在當(dāng)前位置我們需要插入兩個(gè)后綴ab和b, 這是因?yàn)椋?br>
來源于上一個(gè)步驟的后綴a并沒有被合適的插入. 所以它被留了下來，并且由于我們已經(jīng)前進(jìn)了一步，這個(gè)后綴已經(jīng)由a擴(kuò)展成了ab。
我們?cè)谶@一步還需要插入新的后綴b。
在實(shí)踐中這代表我們需要到active point(此時(shí)它指向現(xiàn)在是abcab的邊的字符a后面)，插入當(dāng)前需要插入的后綴b。但是：再一次，事實(shí)證明，b也已經(jīng)在這條邊上出現(xiàn)了。
所以，再一次，我們不去改變樹的結(jié)構(gòu)，我們僅僅：
把活動(dòng)點(diǎn)的值更新為(root, ‘a(chǎn)’, 2)（跟之前同一個(gè)節(jié)點(diǎn)同一條邊，但是我們現(xiàn)在指向了b的后面）。
將remainder的值更新為3因?yàn)閬碜郧耙徊降倪呂覀冞€沒有插入，這一步的邊也同樣沒有插入。
為了讓解釋更清楚一點(diǎn)：在這一步我們需要插入后綴ab和b, 但是因?yàn)閍b已經(jīng)在樹里面了，所以我們只是更新了活動(dòng)點(diǎn)并且連b都沒有嘗試去插入。為什么？因?yàn)槿绻鸻b在樹里面，那么ab的所有后綴(包含b)肯定都已經(jīng)在樹里面了，或許它只是被隱式的包含在里面，但是它肯定在里面，這是由我們當(dāng)前構(gòu)造樹的方式所決定的特性。
通過增加#的值我們前進(jìn)到步驟6，現(xiàn)在樹被自動(dòng)更新成了這樣：
因?yàn)楫?dāng)前remainder的值是3，我們需要插入abx, bx, x。活動(dòng)點(diǎn)告訴了我們ab在哪里結(jié)束，所以我們只需要跳到那個(gè)位置插入x就行了。事實(shí)上，x并沒有在那里，所以我們把邊abcabx分裂開來并且插入一個(gè)中間節(jié)點(diǎn)：
這些邊依然是用兩個(gè)指針來指代所代表的后綴，所以分裂和插入一個(gè)中間節(jié)點(diǎn)可以在O(1)時(shí)間內(nèi)完成。
所以我們現(xiàn)在已經(jīng)處理完了abx而且將remainder的值減少到了2?，F(xiàn)在我們需要插入下一個(gè)被遺留下來的后綴，bx。但是在此之前我們我們需要更新活動(dòng)點(diǎn)。在這種情況下，即分裂一條邊并插入一個(gè)新節(jié)點(diǎn)的情況下，更新活動(dòng)點(diǎn)的規(guī)則，在下面被稱作規(guī)則1，這條規(guī)則在任意活動(dòng)點(diǎn)的active_node是root的時(shí)候都適用(我們?cè)谙旅鎸⒂懻撨m用于其他情況的rule3)，這是規(guī)則1：
在根節(jié)點(diǎn)完插入一個(gè)新節(jié)點(diǎn)后：
active_node 依然還是root。
active_edge 被設(shè)置成了我們需要插入的下一個(gè)后綴的首個(gè)字符, 即 b
active_length 的值減一
因此，新的 活動(dòng)點(diǎn)元組(root, ‘b’, 1)表示我們的下一次節(jié)點(diǎn)插入需要在邊bcabx的一個(gè)位置之后。即b的后面。我們可以在O(1)的時(shí)間復(fù)雜度里面確定下一次插入的位置并且確認(rèn)x是否已經(jīng)存在。如果x已經(jīng)存在了，我們需要停止當(dāng)前的步驟并且讓一切都保持現(xiàn)狀。但是x并不存在，所以我們通過分裂邊來將其插入：
同樣，這將花費(fèi)O(1)的時(shí)間，然后我們將remainder更新為1并且根據(jù)規(guī)則1把a(bǔ)ctive point更新為(root, ‘x’, 0)。
但是在這里我們還有一件事情需要做，我們將其稱為規(guī)則2:
如果我們分裂了一條邊并且插入了一個(gè)新的節(jié)點(diǎn)，并且這個(gè)節(jié)點(diǎn)不是在這個(gè)步驟中插入的第一個(gè)節(jié)點(diǎn)，我們將用一個(gè)特別的指針將前一個(gè)插入的節(jié)點(diǎn)與這個(gè)新節(jié)點(diǎn)連接起來，我們將這個(gè)連接稱為Suffix link。
在接下來我們將會(huì)看到為什么我們要這么做。我們現(xiàn)在的樹結(jié)構(gòu)如下所示，Suffix link使用虛線表示：
我們還需要插入在這這一步驟中需要插入的最后一個(gè)后綴，x。因?yàn)榛顒?dòng)點(diǎn)的active_length屬性已經(jīng)變成了0，新邊的插入將直接在根節(jié)點(diǎn)進(jìn)行。因?yàn)楫?dāng)前從根節(jié)點(diǎn)出發(fā)的邊中沒有以x開頭的，我們將插入一條新邊：
正如我們能夠在圖中看到的，在當(dāng)前步驟中需要插入的所有節(jié)點(diǎn)都已經(jīng)被正確放入了。
通過將#設(shè)置為7我們進(jìn)行到步驟7，像往常一樣，這將會(huì)自動(dòng)在所有的葉節(jié)點(diǎn)的末尾添加字符新字符a。然后我們嘗試在活動(dòng)點(diǎn)插入最后需要插入的那個(gè)后綴a(在根節(jié)點(diǎn)), 然后會(huì)發(fā)現(xiàn)a已經(jīng)被包含了。所以我們結(jié)束當(dāng)前步驟，不插入任何新的邊或者是節(jié)點(diǎn)，將active point 更新為(root, ‘a(chǎn)’, 1)。
在步驟8，#=8，我們連接了新字符b, 并且跟我們?cè)谇懊婵吹降囊粯樱?這代表我們會(huì)更新活動(dòng)點(diǎn)為(root, ‘a(chǎn)’, 2)并將remainder增加一，因?yàn)閎已經(jīng)被包含了。但是，我們發(fā)現(xiàn)（在O(1)的時(shí)間復(fù)雜度內(nèi)）現(xiàn)在活動(dòng)點(diǎn)已經(jīng)在這條邊的結(jié)尾了。我們通過將活動(dòng)點(diǎn)更新為(node1,’\0x’,0)來反映這一變化。在這里，我是用node1來表示邊ab結(jié)束的那個(gè)節(jié)點(diǎn)。
然后，在步驟#=9, 我們需要插入字符c, 這將會(huì)幫助我們理解最后一個(gè)技巧：
第二次擴(kuò)展：使用suffix links
跟以前一樣，對(duì)#的更新自動(dòng)在所有葉節(jié)點(diǎn)連接了字符c并且我們到活動(dòng)點(diǎn)去判斷是否能插入c。結(jié)果我們發(fā)現(xiàn)c已經(jīng)存在了，所以我們除了將活動(dòng)點(diǎn)設(shè)置為(node1, ‘c’, 1)，增加reaminder之外其他什么操作都不做。
現(xiàn)在我們到了第十步，remainder的值為4，所以我們首先需要通過在活動(dòng)點(diǎn)插入d來插入后綴abcd(這可是在三個(gè)步驟之前遺留下來的)。
嘗試在活動(dòng)點(diǎn)插入d會(huì)導(dǎo)致一次O(1)時(shí)間復(fù)雜度的邊分裂：
active_node, 被分裂的邊開始的節(jié)點(diǎn)，在上圖中被標(biāo)記成了紅色。一下是最后的一條規(guī)則，規(guī)則3:
在一個(gè)非根節(jié)點(diǎn)的 active_node上完成了一次邊的分裂后，如果存在一條從這個(gè)節(jié)點(diǎn)開始的suffix link, 我們將會(huì)跟隨這條suffix link將active_node設(shè)置成suffix link指向的節(jié)點(diǎn)。如果沒有suffix link, 那我們將active_node設(shè)置成根節(jié)點(diǎn)，active_edge和active_length保持不變。
所以現(xiàn)在活動(dòng)點(diǎn)變成了(node2, ‘c’, 1), node2在下文中被標(biāo)記成了紅色。
既然abcd的插入已經(jīng)完成了，我們將remainder減少為3并且開始考慮下一個(gè)需要被插入的后綴，bcd。Rule3已經(jīng)將活動(dòng)節(jié)點(diǎn)和活動(dòng)邊設(shè)置成了正確的值所以我們現(xiàn)在只需要簡(jiǎn)單的在活動(dòng)點(diǎn)插入字符d就能完成bcd的插入。
這將導(dǎo)致一次邊的分裂，并且由于規(guī)則2，我們必須創(chuàng)建一個(gè)從前一個(gè)插入的節(jié)點(diǎn)指向這個(gè)節(jié)點(diǎn)的suffix link：
我們觀察到：suffix link能幫助我們更新活動(dòng)點(diǎn)的值讓我們能夠在O(1)的時(shí)間內(nèi)完成新邊的插入。通過上圖，我們可以確認(rèn)ab的結(jié)尾被正確的鏈接到了它的后綴b, 并且節(jié)點(diǎn)abc被鏈接到了bc。
當(dāng)前的步驟到現(xiàn)在并沒有結(jié)束。remainder現(xiàn)在的值是2，并且我們需要跟隨規(guī)則3去再次重置活動(dòng)點(diǎn)。由于當(dāng)前的active_node沒有suffix link, 我們將active_node設(shè)置為root?，F(xiàn)在活動(dòng)點(diǎn)變成了(root, ‘c’, 1)。
因此，下一次插入出現(xiàn)在從根節(jié)點(diǎn)出發(fā)的一條label以c開頭的邊：cabxabcd上，在其第一個(gè)字符之后，即c的后面。這將導(dǎo)致下一次分裂：
并且由于這包含了新建一個(gè)中間節(jié)點(diǎn)，我們根據(jù)規(guī)則2設(shè)置一條來自上一個(gè)新中間節(jié)點(diǎn)的suffix link：
(我使用 Graphviz Dot來制圖.新的suffix link導(dǎo)致了所有已存在的邊的位置被改變了，所以請(qǐng)?jiān)敿?xì)的確認(rèn)上面只是添加了一個(gè)新的suffix link.)。
有了這個(gè)，remainder可以設(shè)置為1，并且由于active_node是root，我們使用規(guī)則1將活動(dòng)點(diǎn)更新為（root，'d'，0）。 這意味著當(dāng)前步驟的最終插入是在根處插入一個(gè)d：
這就是最后的一個(gè)步驟現(xiàn)在我們已經(jīng)完成了。盡管如此，還是有很多最終觀察：
在每一步中我們將#向前移動(dòng)一個(gè)位置，這將會(huì)在O(1)的時(shí)間內(nèi)更新所有的葉節(jié)點(diǎn)。
但這并不能處理由之前步驟遺留下來的后綴，也不能處理當(dāng)前步驟的那個(gè)新的單字符后綴。
reaminder告訴了我們我們還需要插入多少后綴。這些插入與以當(dāng)前位置＃結(jié)尾的字符串的最終后綴一一對(duì)應(yīng)。我們一個(gè)接一個(gè)地考慮并進(jìn)行插入。重要提示：每次插入都在O（1）時(shí)間內(nèi)完成，因?yàn)榛顒?dòng)點(diǎn)告訴我們確切的路線，我們只需要在活動(dòng)點(diǎn)添加一個(gè)單獨(dú)的字符。為什么？ 因?yàn)槠渌址请[式包含的（否則活動(dòng)點(diǎn)不會(huì)在它所在的位置）。
在每一次插入完成后，我們減少remainder的值，如果有suffix link的話，跟隨suffix link更新active_node,如果沒有的話就回到根節(jié)點(diǎn)。如果我們已經(jīng)在根節(jié)點(diǎn)了，就根據(jù)規(guī)則1來修改actiev_point的值。在任何情況下，這都只需要花費(fèi)O(1)的時(shí)間。
如果在其中一個(gè)插入過程中發(fā)現(xiàn)我們要插入的字符已經(jīng)存在，那么即使remainder> 0，我們也不會(huì)做任何事情并結(jié)束當(dāng)前步驟。這是因?yàn)槿魏纹渌覀冞€需要插入的后綴都當(dāng)會(huì)是這個(gè)被包含了的后綴的后綴。因此它們都被隱式包含了。remainder > 0的事實(shí)可以確保我們稍后處理剩余的后綴。
如果在所有的操作都已經(jīng)完成之后reaminder>0會(huì)怎么樣？只要文本的結(jié)尾是之前某處出現(xiàn)過的子字符串，就會(huì)出現(xiàn)這種情況。在這種情況下，我們必須在字符串的末尾附加一個(gè)額外的沒有出現(xiàn)過的字符。在文獻(xiàn)中，美元符號(hào)$通常被用來達(dá)到這個(gè)目的。為什么這很重要？ - >如果以后我們使用完整的后綴樹來搜索后綴，那么只有當(dāng)它們結(jié)束于葉子時(shí)，我們才能接受匹配。否則，我們會(huì)得到大量虛假匹配，因?yàn)闃渲须[含的許多字符串不是主字符串的實(shí)際后綴。在最后強(qiáng)制余數(shù)為0基本上是確保所有后綴在葉節(jié)點(diǎn)處結(jié)束的一種方式。但是，如果我們想要使用樹來搜索一般的子字符串，而不僅僅是主字符串的后綴，那么最后一步確實(shí)不是必需的，正如OP的下面的評(píng)論所建議的那樣。
那么整個(gè)算法的復(fù)雜度是多少？如果文本長(zhǎng)度為n個(gè)字符，顯然有n個(gè)步驟（如果我們添加美元符號(hào)，則n + 1）。在每一步中，我們或者什么都不做（除了更新變量），或者我們做余數(shù)插入，每次都花費(fèi)O（1）時(shí)間。因?yàn)閞emainder表示了我們有多少次在一個(gè)步驟中什么都沒有做，并且每一次插入新的字符的時(shí)候都會(huì)遞減，我們做一些操作的總次數(shù)是n(n + 1)。因此，總的時(shí)間復(fù)雜度是O(n)。
然而，有一件事我沒有正確解釋：可能發(fā)生的情況是，我們遵循后綴鏈接，更新活動(dòng)點(diǎn)，然后發(fā)現(xiàn)其active_length組件不適用于新的活動(dòng)節(jié)點(diǎn)。 例如，考慮這樣的情況：
（虛線表示樹的其余部分，點(diǎn)線表示后綴鏈接。）
現(xiàn)在讓活動(dòng)點(diǎn)成為（紅色，’d'，3），因此它指向defg邊的f后面的位置。現(xiàn)在假設(shè)我們進(jìn)行了必要的更新，現(xiàn)在按照規(guī)則3跟隨后綴鏈接更新活動(dòng)點(diǎn)。新的活動(dòng)點(diǎn)是（綠色，'d'，3）。但是，從綠色節(jié)點(diǎn)出來的d邊是de，所以它只有2個(gè)字符。為了找到正確的活動(dòng)點(diǎn)，我們顯然需要沿著那條邊到達(dá)藍(lán)色節(jié)點(diǎn)并重置為（藍(lán)色，'f'，1）。
在特別糟糕的情況下，active_length可能與remainder一樣大，而remainder可能會(huì)有n那么大。為了找到正確的活動(dòng)點(diǎn)，我們可能不僅需要跳過一個(gè)內(nèi)部節(jié)點(diǎn)，最壞的情況下甚至可以達(dá)到n個(gè)。在每一步中，remainder通常是O(n)，在跟隨后綴鏈接后對(duì)主動(dòng)節(jié)點(diǎn)的后期調(diào)整也可能是O(n), 這是否意味著該算法具有隱藏的O(n^2)復(fù)雜度？
不，原因是如果我們必須調(diào)整活動(dòng)點(diǎn)（例如，如上所述從綠色變?yōu)樗{(lán)色），那么我們將會(huì)被帶到具有其自己的后綴鏈接的新節(jié)點(diǎn)，并且active_length將減小。當(dāng)我們跟隨后綴鏈接鏈更新活動(dòng)點(diǎn)時(shí)，我們做了插入，所以active_length只能減少，并且在任何給定時(shí)間，我們可以在路徑上做的活動(dòng)點(diǎn)調(diào)整的數(shù)量不能大于active_length。由于active_length永遠(yuǎn)不會(huì)大于remainder，并且remainder不僅在每一步中都是O(n)，而且在整個(gè)過程中remainder的增量的總和也是O(n)，因此， 活動(dòng)點(diǎn)調(diào)整也受到O（n）的限制。
