Ukkonen's suffix tree algorithm in plain English原文地址(最高票答案)
下文將嘗試描述Ukkonen算法，我們首先會(huì)展示在字符串比較簡(jiǎn)單的情況下（即：字符串中沒(méi)有重復(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è)的字符來(lái)標(biāo)記一條邊攻礼，而是使用一對(duì)整數(shù)[from, to].它們是指向文本的指針业踢。在這樣的一個(gè)場(chǎng)景下，一條邊攜帶了一個(gè)任意長(zhǎng)度的字符串礁扮，但是只使用了O(1) 的空間（兩根指針）知举。
基本原理
我將先展示如何給一個(gè)特別簡(jiǎn)單的字符串構(gòu)造后綴樹(shù)，一個(gè)沒(méi)有重復(fù)字符的字符串：
abc
該算法從左到右一步一步的運(yùn)行工作太伊。字符串中的每一個(gè)字符都有一個(gè)步驟雇锡。每一個(gè)步驟可能涉及到多個(gè)單獨(dú)的操作，但是我們會(huì)看到（最終觀察結(jié)果）操作總數(shù)為O（n）僚焦。
所以锰提，我們從左側(cè)開(kāi)始，并且首先通過(guò)創(chuàng)建一條從根節(jié)點(diǎn)root(在左邊)到一個(gè)葉節(jié)點(diǎn)的邊插入一個(gè)單獨(dú)的字符a，并且將這條邊標(biāo)記為[0, #]. [0, #]這個(gè)標(biāo)記所表達(dá)的意思是這條邊被用來(lái)表示當(dāng)前字符串從0位置開(kāi)始到當(dāng)前位置結(jié)束的子串立肘。其中#表示的就是當(dāng)前位置边坤。在這一步，當(dāng)前位置是1(即a的后面)谅年。
所以我們有了一顆初始狀態(tài)的樹(shù)惩嘉，它看起來(lái)長(zhǎng)這樣：
而它的意義是這樣的：
現(xiàn)在我們前進(jìn)到位置2（b的后面）。我們?cè)谒惴ǖ拿恳徊降哪繕?biāo)是：將到當(dāng)前位置為止的所有后綴都插入到后綴樹(shù)中踢故。我們通過(guò)一下方式達(dá)到這一目的：
將當(dāng)前a邊擴(kuò)展成為ab文黎。
為后綴b插入一條新的邊。
在我們當(dāng)前的表示中看起來(lái)像這樣：
它的意義是這樣的：
我們觀察到兩件事：
現(xiàn)在表示ab的邊跟它之前在初始樹(shù)中的表示是一樣的：[0, #]殿较。 它所表達(dá)的意思被自動(dòng)更新了因?yàn)槲覀儗?的值從1更新到了2 耸峭。
每一條邊占用的空間都是固定的，因?yàn)樗鼈冎话瑑蓚€(gè)指向文本的指針淋纲，不論它們所表示的子串有多長(zhǎng)劳闹。
接下來(lái)我們?cè)俅胃庐?dāng)前位置，更新我們的樹(shù)結(jié)構(gòu)洽瞬，給每一條已存在的邊連接字符串c并且為新的后綴c插入一條新的邊本涕。
在我們的表示中看起來(lái)是這樣的：
而它的意義是這樣的：
我們可以觀察到：
在每一個(gè)步驟完成的時(shí)候，我們的樹(shù)都是正確包含所有后綴的的后綴樹(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)在來(lái)看一個(gè)更真實(shí)的字符串：
abcabxabcd
這個(gè)字符串以前例中abc為開(kāi)頭鞋喇，然后ab重復(fù)出現(xiàn)声滥，后面跟隨不重復(fù)的x, 然后abc重復(fù)出現(xiàn)，最后以d結(jié)尾侦香。
步驟1到3: 在進(jìn)行了前面三步之后我們從前例中獲得了這樣的一顆后綴樹(shù)：
步驟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)在我們還沒(méi)有用過(guò)它們：
active point, 這是一個(gè)三元組 (active_node, active_edge, active_length).
remainder, 一個(gè)用來(lái)表示我們還剩下多少個(gè)后綴需要插入的整數(shù)仰挣。
這兩個(gè)變量的含義將會(huì)很快的變得清晰起來(lái)伴逸，但是現(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è)元組來(lái)表示這個(gè)信息。
在每一步開(kāi)始之前remainder都總是被設(shè)置成1顷锰。這代表我們?cè)诿恳徊街行枰迦氲暮缶Y數(shù)量都是1（總是最后那個(gè)字符）柬赐。
現(xiàn)在情況開(kāi)始不一樣了。當(dāng)我們嘗試將現(xiàn)在需要插入的最后那個(gè)字符a插入到根節(jié)點(diǎn)的時(shí)候官紫，我們會(huì)發(fā)現(xiàn)現(xiàn)在已經(jīng)有一條從節(jié)點(diǎn)出來(lái)的以a開(kāi)頭的邊肛宋，具體來(lái)說(shuō)：abca這條邊。當(dāng)遇到這種情況的時(shí)候我們這樣做：
我們不在根節(jié)點(diǎn)插入新邊[4,#]束世。相反酝陈，我們發(fā)現(xiàn)后綴a已經(jīng)在樹(shù)里面了。它在一條更長(zhǎng)的邊的中間結(jié)束毁涉，但我們不去管它沉帮，直接讓它保持它現(xiàn)在的樣子就行了。
我們將active point的值更新為(root, ‘a(chǎn)’, 1) 贫堰。這代表我們現(xiàn)在的活動(dòng)點(diǎn)更新為了從根節(jié)點(diǎn)出發(fā)的一個(gè)以a開(kāi)頭的邊的某處穆壕。根據(jù)active_length, 我們知道是在這條邊開(kāi)始的一個(gè)位置之后。我們發(fā)現(xiàn)具體的邊是由其首個(gè)字符指定的其屏。這樣就足夠了因?yàn)樵谀硞€(gè)節(jié)點(diǎn)處以某一個(gè)特定字符開(kāi)始的邊只可能有一條(通過(guò)完整的閱讀本文你會(huì)發(fā)現(xiàn)這是正確的)喇勋。
我們還會(huì)將remainder的值增加一，所以在下一個(gè)步驟開(kāi)始的時(shí)候remainder的值將會(huì)為2 偎行。
觀察：當(dāng)我們需要插入的最后那個(gè)后綴已經(jīng)出現(xiàn)在樹(shù)里面的時(shí)候茄蚯，樹(shù)本身并沒(méi)有被改變(我們只更新active point和remainder)。現(xiàn)在這棵樹(shù)已經(jīng)不再是到當(dāng)前位置為止的后綴樹(shù)的準(zhǔn)確表示了睦优，但是它的確包含了所有的后綴(因?yàn)樽詈笮枰迦氲哪莻€(gè)后綴a已經(jīng)被隱式包含了)渗常。因此，除了更新我們的變量之外（所有的這些變量都是固定長(zhǎng)度的汗盘，時(shí)間復(fù)雜度是O(1)）皱碘， 我們?cè)谶@一步?jīng)]有做其他任何事情。
步驟5: 我們把代表當(dāng)前位置的#更新為5隐孽，這將會(huì)自動(dòng)把樹(shù)結(jié)構(gòu)更新為這樣：
并且因?yàn)閞emainder是2癌椿，在當(dāng)前位置我們需要插入兩個(gè)后綴ab和b, 這是因?yàn)椋?br>
來(lái)源于上一個(gè)步驟的后綴a并沒(méi)有被合適的插入. 所以它被留了下來(lái)，并且由于我們已經(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)了琳钉。
所以势木，再一次，我們不去改變樹(shù)的結(jié)構(gòu)歌懒，我們僅僅：
把活動(dòng)點(diǎn)的值更新為(root, ‘a(chǎn)’, 2)（跟之前同一個(gè)節(jié)點(diǎn)同一條邊啦桌，但是我們現(xiàn)在指向了b的后面）。
將remainder的值更新為3因?yàn)閬?lái)自前一步的邊我們還沒(méi)有插入及皂，這一步的邊也同樣沒(méi)有插入甫男。
為了讓解釋更清楚一點(diǎn)：在這一步我們需要插入后綴ab和b, 但是因?yàn)閍b已經(jīng)在樹(shù)里面了，所以我們只是更新了活動(dòng)點(diǎn)并且連b都沒(méi)有嘗試去插入验烧。為什么查剖？因?yàn)槿绻鸻b在樹(shù)里面，那么ab的所有后綴(包含b)肯定都已經(jīng)在樹(shù)里面了噪窘，或許它只是被隱式的包含在里面笋庄，但是它肯定在里面，這是由我們當(dāng)前構(gòu)造樹(shù)的方式所決定的特性倔监。
通過(guò)增加#的值我們前進(jìn)到步驟6直砂，現(xiàn)在樹(shù)被自動(dòng)更新成了這樣：
因?yàn)楫?dāng)前remainder的值是3，我們需要插入abx, bx, x浩习【苍荩活動(dòng)點(diǎn)告訴了我們ab在哪里結(jié)束，所以我們只需要跳到那個(gè)位置插入x就行了谱秽。事實(shí)上洽蛀，x并沒(méi)有在那里，所以我們把邊abcabx分裂開(kāi)來(lái)并且插入一個(gè)中間節(jié)點(diǎn)：
這些邊依然是用兩個(gè)指針來(lái)指代所代表的后綴疟赊，所以分裂和插入一個(gè)中間節(jié)點(diǎn)可以在O(1)時(shí)間內(nèi)完成郊供。
所以我們現(xiàn)在已經(jīng)處理完了abx而且將remainder的值減少到了2。現(xiàn)在我們需要插入下一個(gè)被遺留下來(lái)的后綴近哟，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并不存在肌似，所以我們通過(guò)分裂邊來(lái)將其插入：
同樣费就，這將花費(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)連接起來(lái)眠蚂，我們將這個(gè)連接稱為Suffix link。
在接下來(lái)我們將會(huì)看到為什么我們要這么做斗躏。我們現(xiàn)在的樹(shù)結(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ā)的邊中沒(méi)有以x開(kāi)頭的隧饼，我們將插入一條新邊：
正如我們能夠在圖中看到的沈堡，在當(dāng)前步驟中需要插入的所有節(jié)點(diǎn)都已經(jīng)被正確放入了。
通過(guò)將#設(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é)尾了热康。我們通過(guò)將活動(dòng)點(diǎn)更新為(node1,’\0x’,0)來(lái)反映這一變化沛申。在這里，我是用node1來(lái)表示邊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趁桃，所以我們首先需要通過(guò)在活動(dòng)點(diǎn)插入d來(lái)插入后綴abcd(這可是在三個(gè)步驟之前遺留下來(lái)的)。
嘗試在活動(dòng)點(diǎn)插入d會(huì)導(dǎo)致一次O(1)時(shí)間復(fù)雜度的邊分裂：
active_node, 被分裂的邊開(kāi)始的節(jié)點(diǎn)肄鸽，在上圖中被標(biāo)記成了紅色卫病。一下是最后的一條規(guī)則，規(guī)則3:
在一個(gè)非根節(jié)點(diǎn)的 active_node上完成了一次邊的分裂后典徘，如果存在一條從這個(gè)節(jié)點(diǎn)開(kāi)始的suffix link, 我們將會(huì)跟隨這條suffix link將active_node設(shè)置成suffix link指向的節(jié)點(diǎn)蟀苛。如果沒(méi)有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并且開(kāi)始考慮下一個(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)完成新邊的插入。通過(guò)上圖蝶念，我們可以確認(rèn)ab的結(jié)尾被正確的鏈接到了它的后綴b, 并且節(jié)點(diǎn)abc被鏈接到了bc抛腕。
當(dāng)前的步驟到現(xiàn)在并沒(méi)有結(jié)束。remainder現(xiàn)在的值是2媒殉，并且我們需要跟隨規(guī)則3去再次重置活動(dòng)點(diǎn)担敌。由于當(dāng)前的active_node沒(méi)有suffix link, 我們將active_node設(shè)置為root。現(xiàn)在活動(dòng)點(diǎn)變成了(root, ‘c’, 1)廷蓉。
因此全封，下一次插入出現(xiàn)在從根節(jié)點(diǎn)出發(fā)的一條label以c開(kāi)頭的邊：cabxabcd上，在其第一個(gè)字符之后桃犬，即c的后面刹悴。這將導(dǎo)致下一次分裂：
并且由于這包含了新建一個(gè)中間節(jié)點(diǎn)，我們根據(jù)規(guī)則2設(shè)置一條來(lái)自上一個(gè)新中間節(jié)點(diǎn)的suffix link：
(我使用 Graphviz Dot來(lái)制圖.新的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)送讲。
但這并不能處理由之前步驟遺留下來(lái)的后綴，也不能處理當(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,如果沒(méi)有的話就回到根節(jié)點(diǎn)善茎。如果我們已經(jīng)在根節(jié)點(diǎn)了，就根據(jù)規(guī)則1來(lái)修改actiev_point的值频轿。在任何情況下垂涯，這都只需要花費(fèi)O(1)的時(shí)間。
如果在其中一個(gè)插入過(guò)程中發(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)過(guò)的子字符串册招，就會(huì)出現(xiàn)這種情況。在這種情況下勒极，我們必須在字符串的末尾附加一個(gè)額外的沒(méi)有出現(xiàn)過(guò)的字符是掰。在文獻(xiàn)中，美元符號(hào)$通常被用來(lái)達(dá)到這個(gè)目的河质。為什么這很重要冀惭？ - >如果以后我們使用完整的后綴樹(shù)來(lái)搜索后綴震叙，那么只有當(dāng)它們結(jié)束于葉子時(shí)，我們才能接受匹配散休。否則媒楼，我們會(huì)得到大量虛假匹配，因?yàn)闃?shù)中隱含的許多字符串不是主字符串的實(shí)際后綴戚丸。在最后強(qiáng)制余數(shù)為0基本上是確保所有后綴在葉節(jié)點(diǎn)處結(jié)束的一種方式划址。但是，如果我們想要使用樹(shù)來(lái)搜索一般的子字符串限府，而不僅僅是主字符串的后綴夺颤，那么最后一步確實(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è)步驟中什么都沒(méi)有做褐啡，并且每一次插入新的字符的時(shí)候都會(huì)遞減诺舔，我們做一些操作的總次數(shù)是n(n + 1)。因此备畦，總的時(shí)間復(fù)雜度是O(n)低飒。
然而，有一件事我沒(méi)有正確解釋：可能發(fā)生的情況是萍恕，我們遵循后綴鏈接逸嘀，更新活動(dòng)點(diǎn)，然后發(fā)現(xiàn)其active_length組件不適用于新的活動(dòng)節(jié)點(diǎn)允粤。 例如崭倘，考慮這樣的情況：
（虛線表示樹(shù)的其余部分，點(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)出來(lái)的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)抒钱，我們可能不僅需要跳過(guò)一個(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è)過(guò)程中remainder的增量的總和也是O(n)，因此照棋， 活動(dòng)點(diǎn)調(diào)整也受到O（n）的限制资溃。
