簡單英語中的Ukkonen后綴樹算法在這一點(diǎn)上我覺得有點(diǎn)厚。我花了幾天的時(shí)間試圖把我的頭完全集中在后綴樹的構(gòu)造上，但由于我沒有數(shù)學(xué)背景，所以很多解釋都沒有得到解釋，因?yàn)樗鼈冮_始過度使用數(shù)學(xué)符號(hào)。我發(fā)現(xiàn)最接近正確解釋的是帶后綴樹的快速字符串搜索，但他掩蓋了不同的點(diǎn)和一些方面的算法仍然不清楚。我確信，在堆棧溢出的情況下，一步地解釋這個(gè)算法對(duì)于除我之外的其他許多人來說都是非常寶貴的。作為參考，以下是Ukkonen關(guān)于該算法的論文：http：/www.cs.helsinki.fi/u/Ukkonen/SuffixT1withFigs.pdf到目前為止，我的基本理解是：我需要遍歷給定字符串T的每個(gè)前綴P我需要遍歷前綴P中的每個(gè)后綴S并將其添加到樹中要向樹中添加后綴S，我需要遍歷S中的每個(gè)字符，迭代包括沿著現(xiàn)有的分支遍歷，該分支以S中的同一組字符C開頭，當(dāng)我到達(dá)后綴中的不同字符時(shí)，可能會(huì)將邊分割為后代節(jié)點(diǎn)，或者如果沒有匹配的邊向下行走。當(dāng)C沒有找到匹配的邊時(shí)，就會(huì)為C創(chuàng)建一個(gè)新的葉子邊緣?；舅惴ㄋ坪跏荗(N)2)，正如在大多數(shù)解釋中所指出的那樣，由于我們需要遍歷所有前綴，那么我們需要遍歷每個(gè)前綴的每個(gè)后綴。Ukkonen的算法顯然是獨(dú)一無二的，因?yàn)樗褂昧撕缶Y指針技術(shù)，盡管我認(rèn)為那，那個(gè)我很難理解。我也很難理解：指定、使用和更改“活動(dòng)點(diǎn)”的確切時(shí)間和方式算法的經(jīng)典方面是怎么回事？為什么我看到的實(shí)現(xiàn)需要“修復(fù)”他們使用的邊界變量這是已完成的C#源代碼。它不僅工作正常，而且支持自動(dòng)封圣，并呈現(xiàn)出更好看的輸出文本圖。源代碼和示例輸出位于：https://gist.github.com/2373868更新2017-11-04許多年后，我發(fā)現(xiàn)了后綴樹的新用法，并在JavaScript..蓋斯特在下面。應(yīng)該沒有竊聽器。把它倒入一個(gè)js文件，npm install chalk在相同的位置運(yùn)行node.js，可以看到一些豐富多彩的輸出。在同一個(gè)Gist中有一個(gè)簡化版本，沒有任何調(diào)試代碼。https：/gist.github.com/axe蛙/c347bf0f5e0723cbd09b1aed6ec6fc6