suffix tree
文章出處：http://www.cnblogs.com/snowberg/archive/2011/10/21/2468588.html
3???What is a Suffix Tree
Suffix tree, 或?后綴樹(shù)?，是一種相當(dāng)神奇的數(shù)據(jù)結(jié)構(gòu)，它包含了字符串中的大量信息，能夠用于解決很多復(fù)雜的字符串問(wèn)題 —— 事實(shí)上，基本上目前為止俺遇到過(guò)的所有與字符串有關(guān)的問(wèn)題都可以通過(guò)它解決。
我們以字符串?MISSISSIPPI?為例，先列出它所有的后綴：
1. MISSISSIPPI 2. ISSISSIPPI 3. SSISSIPPI 4. SISSIPPI 5. ISSIPPI 6. SSIPPI 7. SIPPI 8. IPPI 9. PPI A. PI B. I將它們分別插入到?字典樹(shù)?中我們可以得到：
BTW, 樹(shù)中的?$?符號(hào)表示字符串結(jié)尾 —— 這里?I?是字符串?MISSISSIPPI?的結(jié)尾，而?I?又在其中間出現(xiàn)了，所以有必要使用一個(gè)特殊的符號(hào)標(biāo)識(shí)出來(lái)，同理在后綴樹(shù)中也需要有這樣的一個(gè)符號(hào)；雖然 C 語(yǔ)言中有'\0'?，但這里使用?$?符號(hào)似乎屬于約定俗成的事情了，咱這次也就從了它吧。
這樣的一棵字典樹(shù)已經(jīng)具備了后綴樹(shù)的功能 ——
比如說(shuō)吧，你從根節(jié)點(diǎn)開(kāi)始順著這個(gè)字典樹(shù)的隨便一個(gè)樹(shù)枝走 n 步，然后數(shù)一下再往下有幾片葉子，就知道已經(jīng)走過(guò)的這 n 個(gè)字符組成的字符串在原字符串中一共出現(xiàn)過(guò)多少次了 —— 由于你可以把某一節(jié)點(diǎn)下方的葉節(jié)點(diǎn)數(shù)目保存在該節(jié)點(diǎn)中，所以這個(gè)算法實(shí)際上是 O(n) 的，怎么樣？
只是，你也看出來(lái)了，它的空間復(fù)雜度相當(dāng)之高，實(shí)際上基本上沒(méi)有誰(shuí)會(huì)用這樣一個(gè)數(shù)據(jù)結(jié)構(gòu)。
于是，?把所有最近兩個(gè)有多個(gè)分支的節(jié)點(diǎn)之間的部分（它們每個(gè)節(jié)點(diǎn)各自僅有一個(gè)分支）合并起來(lái)?(參考：Patricia Trie?或曰?Radix Tree)，我們可以得到：
這就是一棵后綴樹(shù)了。
順便提一句，雖然邏輯結(jié)構(gòu)如上，但實(shí)際的數(shù)據(jù)結(jié)構(gòu)中存儲(chǔ)的東西大致是這樣的：
這樣，每一條邊占用的空間為常數(shù)大小，于是后綴樹(shù) Tree(T) 的空間復(fù)雜度為 O(|T|)，|T| 為字符串 T 的長(zhǎng)度。?因?yàn)?/strong>?：
- 從樹(shù)根到樹(shù)葉的每一條路徑組成了一個(gè)后綴
- 所以樹(shù)葉的數(shù)量等于后綴的數(shù)量
- 每個(gè)非葉子節(jié)點(diǎn)都有至少兩條樹(shù)枝
- 所以非葉節(jié)點(diǎn)的數(shù)量小于葉節(jié)點(diǎn)的數(shù)量
- 除去根節(jié)點(diǎn)，節(jié)點(diǎn)數(shù)等于邊數(shù)
- 所以，后綴樹(shù)的空間復(fù)雜度為： O(|T| + size(edge labels))?[1]
后綴樹(shù)和?后綴 Trie?一樣包含了整個(gè)字符串中所有子串的信息，又僅占用 O(|T|) 空間，而且 —— 后面會(huì)說(shuō)到，它可以在 O(|T|) 時(shí)間內(nèi)構(gòu)造出來(lái)，這些特性使它成為了一個(gè)理論分析以及實(shí)際應(yīng)用上都非常重要的數(shù)據(jù)結(jié)構(gòu)。
4???What Can It Do
后綴樹(shù)的用途是如此之廣以至于 Dan Gusfield 在他的書(shū)中?[2]?花了七十多頁(yè)來(lái)介紹，我在這里先挑幾個(gè)自己看來(lái)比較好玩的例子說(shuō)說(shuō)，以期待激發(fā)讀者的興趣。
4.1???Longest Common Substring
Longest common substring?- 即?最長(zhǎng)公共子串?，是指在兩個(gè)字符串中都出現(xiàn)了的最長(zhǎng)子串 —— 比如，superiorcalifornialives?和?sealiver?的最長(zhǎng)公共子串為?alive?。
這是個(gè)很經(jīng)典的例子，據(jù)說(shuō) 1970 年，后綴樹(shù)的概念還沒(méi)有被提出來(lái)的時(shí)候，Knuth 爺爺曾無(wú)比確信找出兩個(gè)字符串最長(zhǎng)公共子串的線性算法是不存在的?[2]?；然而，在知道后綴樹(shù)的概念之后，這個(gè)算法也顯而易見(jiàn)了：
?
4.2???Exact String Matching
當(dāng)字符串 T 已知且固定不變，P 改變時(shí)：
我們可以用 O(|T|) 時(shí)間預(yù)處理 T，然后在 O(|P|) 時(shí)間內(nèi)回答出 “P 在 T 中出現(xiàn)了幾次？” 或是 “P 在 T 的哪些地方出現(xiàn)過(guò)？” 之類的問(wèn)題：
預(yù)處理 T, 得到它的后綴樹(shù) —— 也可以把多個(gè)字符串 T1, T2 ... 放入同一個(gè)后綴樹(shù)，然后查找 P 時(shí)只需要從這個(gè)后綴樹(shù)的根開(kāi)始順著 P 往下走，然后讀出保存在節(jié)點(diǎn)中的信息 (下方的樹(shù)葉數(shù)量、出現(xiàn)地方 &etc.) 就行了。
而這也就意味著你可以把很大的文檔進(jìn)行?索引?，然后快速的進(jìn)行搜索。
當(dāng)字符串 P 已知且固定不變時(shí)：
我們也可以用 O(|P|) 時(shí)間預(yù)處理模式串 P，然后用 O(|T|) 時(shí)間在 T 中找出 P —— 時(shí)間、空間復(fù)雜度的上界就和 KMP 算法或是 Boyer-Moore 算法一樣。
這個(gè)可能看不明顯，但是，這么說(shuō)吧，KMP 算法中 Next 數(shù)組保存的所有信息、Boyer-Moore 算法中 Bad-Charactor 和 Good-Suffix 表的信息后綴樹(shù)中都有。 由于實(shí)際操作上比較復(fù)雜，這里就不展開(kāi)了，讀者請(qǐng)自行參考?[2]?或者耐心等待?If?(嗯，也就是本人) 心血來(lái)潮的那一天。
當(dāng) P 和 T 都已知的時(shí)候：
很明顯，我們可以在 O(|T| + |P|) 時(shí)間內(nèi)找出 P 在 T 中的出現(xiàn)，不說(shuō)了。
4.3???Ziv-Lempel Compression
嗯，常說(shuō)的 LZ77 指的就是 Lempel Ziv 1977。
Ziv-Lempel 壓縮的主要思想是，將前方出現(xiàn)過(guò)的子串使用?(位置, 長(zhǎng)度) 對(duì)?表示出來(lái)，例如aaaaaaaaaaaaaaaa?就可以表示為?a(1,1)(1,2)(1,4)(1,8)?：
a(1,1) == aa aa(1,2) == aaaa aaaa(1,4) == aaaaaaaa aaaaaaaa(1,8) == aaaaaaaaaaaaaaaa真正的 LZ 編碼方式和這里說(shuō)的有點(diǎn)區(qū)別，但思想是一樣的。
有了后綴樹(shù)，LZ 壓縮也簡(jiǎn)單了：
以上查找 (位置, 長(zhǎng)度) 序列的算法時(shí)間復(fù)雜度是 O(長(zhǎng)度)，于是壓縮算法整體復(fù)雜度就是 O(|T|) 。
—— BTW，后面會(huì)說(shuō)到，根據(jù) Ukkonen 的算法?[3]?，后綴樹(shù)本身可以 "On-line" 構(gòu)造，即，每次加入一個(gè)字符，得到當(dāng)前的后綴樹(shù)；這樣， Ziv-Lempel 壓縮也可以僅用一次自左向右的掃描完成。
5???Few New Concepts
在繼續(xù)講如何構(gòu)造后綴樹(shù)之前，為了后面表述的方便，再提幾個(gè)簡(jiǎn)單的概念：
Explicit Node (顯式節(jié)點(diǎn))?：6???How To Build It
目前我只弄懂了 Ukkonen 的算法?[3]?，所以下面也只說(shuō)這一種算法：
6.1???Native Approach
首先，我們觀察發(fā)現(xiàn)，若?S?是一個(gè)非空字符串，?c?是一個(gè)字符，則將?c?加到?S?的每個(gè)后綴（包括空后綴）后面，我們可以得到?Sc?的所有后綴。
Suffixes(a):aSuffixes(ab):abbSuffixes(abc):abcbccSuffixes(abca):abcabcacaa...很顯然，可以將這樣的原理用于構(gòu)建后綴樹(shù)：假設(shè) T[0..i-1] 的后綴樹(shù)已經(jīng)建好了，那么在 T[0..i-1] 的每個(gè)后綴 T[0..i-1], T[1..i-1] .. T[j..i-1] .. T[i-1..i-1] 的后面加上字符 T[i] 就可以得到 T[0..i] 的后綴樹(shù)了。
具體到 “將 T[i] 加到后綴 T[j..i-1]” 的這個(gè)過(guò)程，則有可能遇到三種情況：
這種情況下，只需要把 T[i] 加到該樹(shù)葉的邊上即可。
這種情況下，在 T[j..i-1] 的后面加上樹(shù)葉 T[i]
(可能需要把隱式節(jié)點(diǎn)變換成顯式節(jié)點(diǎn))。
這種情況下，我們什么都不用做。
于是，如果不加任何形式的優(yōu)化，那么 Ukkonen 的算法就是這么回事：
令 n = |T|； 在 T 尾部加上終結(jié)符 $。 for i from 0 to n: // n+1 個(gè)階段（包括加上終結(jié)符）for j from 0 to i-1: // 每個(gè)階段 i 次擴(kuò)展從后綴樹(shù)的根順著 T[ j..i-1 ] 走到節(jié)點(diǎn) v (顯式/隱式)如果 v 下方節(jié)點(diǎn)中存在第一個(gè)字符為 T[i] 的，則什么都不用做。否則如果 v 是隱式節(jié)點(diǎn)，那么：將 v 改成顯式節(jié)點(diǎn)。在 v 下增加葉節(jié)點(diǎn)，從 v 到新節(jié)點(diǎn)的邊標(biāo)記為 T[i]。若 v 是內(nèi)部節(jié)點(diǎn)或根節(jié)點(diǎn)：在 v 下增加葉節(jié)點(diǎn)，從 v 到新節(jié)點(diǎn)的邊標(biāo)記為 T[i]。否則： (只能是葉節(jié)點(diǎn)了)：將 T[i] 加到邊的尾部。具體的，這里給出構(gòu)建?MISSISSIPPI$?的后綴樹(shù)的全過(guò)程，如下：
6.2???Speed Up!
上面的原生態(tài)算法雖通俗易懂老少皆宜，但其時(shí)間復(fù)雜度相當(dāng)之高 ( O(|T|3) )， 想要有實(shí)用價(jià)值必須得提高它的效率 —— 而正如前面提到過(guò)的，其實(shí)后綴樹(shù)可以在 O(|T|) 時(shí)間內(nèi)構(gòu)造；這個(gè) O(|T|) 的奇妙算法和上面的算法主體流程其實(shí)一樣，下面就要介紹加速妙方了，請(qǐng)坐穩(wěn)。
6.2.1???Stop When?T[j..i]?Exists
首先說(shuō)最容易理解的：
很顯然，如果后綴樹(shù) STree(T[0..i-1]) 中已經(jīng)存在 T[j..i] 了，那么 T[j+1 .. i] 肯定也在其中，?因?yàn)?/strong>?：
于是乎，碰到 T[j..i] 存在的情況，就不必繼續(xù)傻乎乎的在樹(shù)中查找 T[j+1 .. i-1], T[j+2 .. i-1] ... 了。
6.2.2???Opened Leaves
若知道了字符串的長(zhǎng)度?l?，又知道了樹(shù)葉的起點(diǎn)?d?，就可以知道這個(gè)樹(shù)葉的邊的長(zhǎng)度為?l?-?d?—— 所以首先，不記錄樹(shù)葉的邊長(zhǎng)并不影響功能。
而如果直接把所有的樹(shù)葉都標(biāo)記為開(kāi)放的，做法例如令其長(zhǎng)度為無(wú)窮大 —— 這樣有一個(gè)好處：在對(duì)樹(shù)葉的擴(kuò)展中就什么都不用做了。
什么時(shí)候可以利用這個(gè)小技巧呢？我們看看將 T[i] 加入到 STree(T[0 .. i-1]) 的過(guò)程：
-
首先， T[0 .. i-1] 肯定停在樹(shù)葉上。
-
假設(shè) STree(T[0 .. i-1]) 有 n 片樹(shù)葉，那么 T[1 .. i-1] T[2 .. i-1], T[n-1 .. i-1] 也都會(huì)停在樹(shù)葉上，因?yàn)?#xff1a;
對(duì)于任何 j < i-1 如果 T[j .. i-1] 不在樹(shù)葉上，那么 T[j+1 .. i-1] 更不可能在樹(shù)葉上；
這又是因?yàn)?#xff0c; T[j+1 .. i-1] 是 T[j .. i-1] 的后綴，若 T[0 .. i-1] 有子串 S = T[j .. i-1]+'c' （因此 T[j .. i-1] 不在樹(shù)葉上），那么 T[0 .. i-1] 肯定也有子串 S[1:] = T[j+1 .. i-1]+'c' （因此 T[j+1 .. i-1] 也不在樹(shù)葉上）。
于是如果 STree(T[0 .. i-1]) 有 n 片樹(shù)葉，那一定就對(duì)應(yīng)著前 n 個(gè)后綴。
所以，已經(jīng)有了 STree(T[0 .. i-1]) 的話，不必沿著 T[0 .. i-1], T[1 .. i-1] .. T[i-1 .. i-1] 所有這些路徑將 T[i] 加入到后綴樹(shù)；而只需要從 n 開(kāi)始沿著路徑 T[n .. i-1], T[n+1 .. i-1] .. T[i-1 .. i-1] 加入 T[i] 。
6.2.3???Count & Skip
再看從后綴樹(shù)的根開(kāi)始查找路徑 T[j .. i-1] 的過(guò)程，不難發(fā)現(xiàn)：
某一條邊上進(jìn)行匹配時(shí)，不必一個(gè)字符一個(gè)字符的比較，而只需要比較第一個(gè)字符，跳過(guò)剩下來(lái)的部分、直接去下一個(gè)節(jié)點(diǎn)，因?yàn)?#xff1a;
6.2.4???Suffix Link
好了，接下來(lái)要講最重要也是最難理解的話題：后綴鏈接了。
6.2.4.1???What is It
用漢語(yǔ)解釋 Suffix link 的話，它就是某種顯式節(jié)點(diǎn)之間的鏈接，其目的是簡(jiǎn)化順著 T[j .. i-1] 找到下一次擴(kuò)展的地方的過(guò)程。
根據(jù)?Count & Skip?的技巧，從根節(jié)點(diǎn)開(kāi)始找到擴(kuò)展點(diǎn)的算法復(fù)雜度已經(jīng)只與下方的分支數(shù)有關(guān)了，如果能直接從某個(gè)很接近擴(kuò)展點(diǎn)的顯式節(jié)點(diǎn)開(kāi)始查找，那么顯然能夠提高效率。
很巧的，我們發(fā)現(xiàn)，如果有某個(gè)內(nèi)部節(jié)點(diǎn)的路徑為?aS，其中?a?是一個(gè)字符、?S?是一個(gè)(可能為空的)字符串，那么肯定也會(huì)有一個(gè)路徑為?S?的內(nèi)部節(jié)點(diǎn)、即使沒(méi)有，也會(huì)在下次擴(kuò)展的時(shí)候產(chǎn)生。
因?yàn)?/strong>： 如果?aS?停在一個(gè)內(nèi)部節(jié)點(diǎn)上面，也就是?aS?后有分支，那么當(dāng)前的 T[0 .. i-1] 肯定有子串?aS+c 以及aS+d （ c 和 d 是不同的兩個(gè)字符） 這兩個(gè)不同的子串，于是肯定也有?S+c 以及?S+d 兩個(gè)子串了。至于“下次擴(kuò)展時(shí)產(chǎn)生”的這種情況，則發(fā)生在已經(jīng)有?aS+c 、?S+c ，剛加入?aS+d （于是產(chǎn)生了新的內(nèi)部節(jié)點(diǎn)），正要加入?S+d 的時(shí)候。
這樣，我們將節(jié)點(diǎn)?aS?指向?S?，并把這樣的一個(gè)指向關(guān)系稱為?aS?的?后綴鏈接?。
見(jiàn)圖中紅色箭頭：
6.2.4.2???How It Works
后綴鏈接有什么用呢？
前面似乎提示過(guò)了，在?aS?后加上了 d 之后，下一個(gè)步驟便是在?S?之后加上 d ；于是同樣，在?aSxy?后加上 z （步驟一）之后，下一個(gè)步驟是在?Sxy?后加上 z （步驟二）。如果?aS?停在了內(nèi)部節(jié)點(diǎn)上，那么?S?也停在內(nèi)部節(jié)點(diǎn)上，那么從步驟一到步驟二，通過(guò)后綴鏈接，可以直接找到路徑為?S?的這個(gè)內(nèi)部節(jié)點(diǎn)；然后通過(guò)Count & Skip?技巧，可以直接定位到?xy?后方的擴(kuò)展點(diǎn)。
參考圖中?A?節(jié)點(diǎn)到?B?節(jié)點(diǎn)的藍(lán)色路徑：
這里用?MISSISSIPPI?的例子來(lái)講后綴鏈接似乎不太合適，參考它的構(gòu)造過(guò)程圖示，第九步之前樹(shù)中一直只有一個(gè)內(nèi)部節(jié)點(diǎn)，第九步?jīng)]有利用后綴鏈接加速，而第九步之后，根據(jù)?Opened Leaves?技巧，只需要對(duì)?P?開(kāi)頭的那一條邊進(jìn)行擴(kuò)展……但這個(gè)例子絕對(duì)不意味著后綴鏈接沒(méi)有用。
嗯，比如說(shuō)，作為一個(gè)正面的案例，構(gòu)建?MISSISSIPPIMISSIA?的后綴樹(shù)的第 17 階段（加入?'A'?），第 13、14、15 次擴(kuò)展便是順著后綴鏈接進(jìn)行的（?ISSI?->?SSI?->?SI?->?I?->?ROOT?）。
6.2.4.3???How To Maintain It
那么如何建立和維護(hù)后綴鏈接呢？
依然根據(jù)上面提到的原理，我們發(fā)現(xiàn)：
在某一階段中，前一次擴(kuò)展訪問(wèn)到（或者建立）的內(nèi)部節(jié)點(diǎn)到本次擴(kuò)展訪問(wèn)到的地方要么已經(jīng)有了一條后綴鏈接，要么就應(yīng)該建立一條后綴鏈接。
因此，具體實(shí)現(xiàn)起來(lái)，我們可以保存一個(gè)最后訪問(wèn)的內(nèi)部節(jié)點(diǎn)的指針?p?，訪問(wèn)到新的內(nèi)部節(jié)點(diǎn)?node?的時(shí)候，將?p?的后綴鏈接指向?node?，再將?p?設(shè)為?node?即可。
6.3???Why O(n)
至于為什么這個(gè)算法是線性的，分析起來(lái)倒是不難：
設(shè) n = |T|。
- 假設(shè)節(jié)點(diǎn) A 的后綴鏈接指向節(jié)點(diǎn) B ，A 的路徑為?pa?, B 的路徑為?pb?， A 上方有?x?個(gè)節(jié)點(diǎn)， B 上方有?y?個(gè)節(jié)點(diǎn)，則有?：
- x?<=?y?+ 1 （因?yàn)?pb?是?pa?的后綴，因此除了第一個(gè)字符之后的分支，?pa?路徑上的其他分支?pb路徑上必然也有，反之則不然）。
- 因此，再看每次顯式擴(kuò)展的過(guò)程：從當(dāng)前位置向下找到擴(kuò)展點(diǎn)；完成擴(kuò)展； 向上一個(gè)節(jié)點(diǎn)；跟隨后綴鏈接來(lái)到下一個(gè)位置。其中除了“從當(dāng)前位置向下找到擴(kuò)展點(diǎn)”這一步之外，剩下的都只需要常數(shù)時(shí)間。
- 而“向下”查找一次之后，跟隨后綴鏈接來(lái)到新的一個(gè)節(jié)點(diǎn)時(shí)最多只能使上方的節(jié)點(diǎn)數(shù)減少 2。
- 后綴樹(shù)整體的深度不超過(guò)?n?，而總共又只有?n?次顯式擴(kuò)展，因此節(jié)點(diǎn)的訪問(wèn)次數(shù)為 O(n)
6.4???C++ Code
最后，以下代碼是我的實(shí)現(xiàn)，使用 boost license 以及 GPL v3 發(fā)布，需要用的話請(qǐng)自由選擇～
使用模板一方面是因?yàn)樽址拇_有不同的類型，另一方面（更主要的）是方便把實(shí)現(xiàn)和定義放在同一個(gè)文件里，以減少鏈接的工作（我懶嘛），用 C 的童鞋，對(duì)不住了。
本人對(duì)下面程序的任何 bug 引起的任何后果不負(fù)任何責(zé)任，但是如果發(fā)現(xiàn)有 bug 請(qǐng)您務(wù)必與俺聯(lián)系。
/** File: suffixtree.h* Author: If* Created on Sep/14th/2010, 14:02** License: GPL v3 / Boost Software License 1.0*//**update: Oct/17th/2010:Record belongTo information on leaves only,other works were left to `dfs`, `bfs` and `eachLeaf`function.*update: Oct/17th/2010:Add `eachLeaf` function, for it's quite useful*//* Permission is hereby granted, free of charge, to any person or organization obtaining a copy of the software and accompanying documentation covered by this license (the "Software") to use, reproduce, display, distribute, execute, and transmit the Software, and to prepare derivative works of the Software, and to permit third-parties to whom the Software is furnished to do so, all subject to the following:The copyright notices in the Software and this entire statement, including the above license grant, this restriction and the following disclaimer, must be included in all copies of the Software, in whole or in part, and all derivative works of the Software, unless such copies or derivative works are solely in the form of machine-executable object code generated by a source language processor.THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. *//* Copyright (C) 2010 IfThis program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.You should have received a copy of the GNU General Public License along with this program. If not, see <http://www.gnu.org/licenses/>. *//* following code may cause permanent brain damage, read at yourown risk. */#ifndef SUFFIXTREE_H #define SUFFIXTREE_H// #define HAS_BOOST#include <functional> #include <algorithm> #include <stdexcept> #include <iterator> #include <iostream> #include <vector> #include <string> #include <stack> #include <queue>#include <assert.h> #include <stdio.h>#ifdef HAS_BOOST #include <boost/pool/object_pool.hpp> #endifusing std::vector; using std::basic_string;#ifdef DEBUG_STREE FILE* __streeLogFile=stderr; #define dbg(...) \ do{ \ fprintf(__streeLogFile, __VA_ARGS__); \ fflush(__streeLogFile); \ } while(0) #define dbg_puts(str, len) \ do{ \ for(int i=0;i<len;++i) \ fputc(str[i], __streeLogFile); \ fflush(__streeLogFile); \ } while(0) #else #define dbg(...) /*nothing at all*/ #define dbg_puts(s, l) /*nothing at all*/ #endiftemplate <class CharT, class Additional=void*> struct Node {// Important members:CharT const* str; // since edge-node has one-to-one correspondenceint len; // there is no need to separate them.int startAt; // for the use of presenting an implicit node.// it will then be the position of first different// charactor.Node * link; // suffix link.Node * parent;vector<Node*> branches;int belongTo; // which string does this leaf belongs to.// *only recorded on leaves*// Misc members:int leafNum; // leaf number ( nth suffix ).int depth; // no need to explain.Additional info; // some more information you need, depending on// your application.Node():str(0),len(0),startAt(0),link(0),parent(0),branches(),belongTo(-1),leafNum(0),depth(0),info(){ }Node(Node const& other):str(other.str),len(other.len),startAt(other.startAt),link(other.link),parent(other.parent),branches(other.branches),belongTo(other.belongTo),leafNum(other.leafNum),depth(other.depth),info(other.info){ }~Node() { }/*static inline int matchFirst(Node const& node, CharT const val){return node.str[0]==val? node.len : 0;}static inline bool ptrMatchFirst(Node const* node, CharT const val){return node->str[0]==val? node->len : 0;}*/struct MatchFirst {CharT val;MatchFirst(CharT v):val(v){ }inline bool operator()(Node const* node) const {return node->str[0]==val;}}; };template <class CharT=char, class T=void*> class SuffixTree { protected:typedef Node<CharT,T> NodeT;typedef typename vector<NodeT*>::iteratorNodeIterator; #ifdef HAS_BOOSTboost::object_pool<NodeT>allNodes_; #endifNodeT* root_;vector<NodeT*> leaves_;vector<NodeT*> allLeaves_;int nLeaves_;vector<basic_string<CharT> >strings_;NodeT* latestInternalNode_;NodeT* currentPos_;int phase_;int extension_;protected:NodeT* allocNode() { #ifdef HAS_BOOSTreturn allNodes_.malloc(); #elsereturn new NodeT; #endif}void freeNode(NodeT *& node) { #ifdef HAS_BOOSTallNodes_.free(node); #elsedelete node; #endifnode = 0;}/*** following str[0:len], and then add str[len] to current tree.** @return true if undone, false if str[0..len] already exists - which means* extension process is done.*/bool extend (CharT const* str, int pos);// follow path "str" from node down.NodeT* jumpDown(CharT const* str, int len, NodeT* node, bool fromFront=0);/*** split one edge from its startAt position.** @param edge: a node with startAt!=0* @param leafLabel: label of the newly created leaf, with length==1* @return newly created leaf.*/NodeT* splitEdge(NodeT* edge, CharT const* leafLabel);void putEnd() {int p = phase_+1;int const nth = strings_.size()-1;for(NodeIterator itr=leaves_.begin(),end=leaves_.end(); itr!=end; ++itr){(*itr)->len = --p - (*itr)->depth;allLeaves_.push_back(*itr);}}#ifndef HAS_BOOSTinline void destroy(NodeT* node) {for(NodeIterator itr=node->branches.begin(), end=node->branches.end();itr!=end; ++itr)destroy(*itr);freeNode(node);} #endifprivate:SuffixTree(SuffixTree<CharT,T> const&); // complicated while useless,// i've got no interest.public:inline SuffixTree();inline SuffixTree(basic_string<CharT> const&);#ifdef HAS_BOOST~SuffixTree() { /*nothing to do*/ } #else~SuffixTree() { destroy(root_); } #endifvoid addString(CharT const * str, int len);void addString(basic_string<CharT> const& str) {addString(str.c_str(), str.length()); // to maintain a copy}NodeT const* root() {return root_;} /*void deleteString(CharT const * str, int len);void deleteString(basic_string<CharT> const& str) {deleteString(str.c_str(), str.length());} */// will call f(node) on each node of this tree, including root.template <class Function>void dfs(Function f) {std::stack<NodeT*> todo;todo.push(root_);while(!todo.empty()) {NodeT* node = todo.top();todo.pop();for(NodeIterator itr=node->branches.begin(),end=node->branches.end();itr!=end;++itr) {todo.push(*itr);}f(*node);}}// will call f(node) on each node of this tree, including root.template <class Function>void bfs(Function f) {std::queue<NodeT*> todo;todo.push(root_);while(!todo.empty()) {NodeT* node = todo.front();todo.pop();for(NodeIterator itr=node->branches.begin(),end=node->branches.end();itr!=end;++itr) {todo.push(*itr);}f(*node);}}template <class Function>void eachLeaf(Function f) {for(NodeIterator itr=allLeaves_.begin(), end=allLeaves_.end();itr!=end; ++itr) {f(**itr);}}// human-readable json-like format outputvoid print(std::basic_ostream<CharT> * stream);// machine-readable dot format output, can be used to// generate graph using Graphvizvoid dot(std::basic_ostream<CharT> * stream); };template <class CharT, class T> SuffixTree<CharT,T>::SuffixTree():root_(0),leaves_(),nLeaves_(0),strings_(),latestInternalNode_(0),currentPos_(0),phase_(0),extension_(0) {root_ = allocNode();root_->parent = root_; // for convenienceroot_->link = root_;root_->len = 0;root_->str = 0;root_->startAt = 0;currentPos_ = root_; }template <class CharT, class T> SuffixTree<CharT,T>::SuffixTree(basic_string<CharT> const& str):root_(0),leaves_(),nLeaves_(0),strings_(),latestInternalNode_(0),currentPos_(0),phase_(0),extension_(0) {root_ = allocNode();root_->parent = root_; // for convenienceroot_->link = root_;root_->len = 0;root_->str = 0;root_->startAt = 0;currentPos_ = root_;this->addString(str); }template <class CharT, class T> void SuffixTree<CharT,T>::addString(CharT const* str, int len) {strings_.push_back(basic_string<CharT>(str, str+len));int whichString = strings_.size()-1;CharT const* cstr = strings_.back().c_str();dbg("adding string \"%s\" to suffix tree ... \n", cstr);root_->len = 0;root_->depth = 0;leaves_ = vector<NodeT*>();nLeaves_=0;currentPos_=root_;for(phase_=0; phase_<=len; ++phase_) { // there's a '\0' behindbool undone = true;latestInternalNode_ = 0;for(int j=nLeaves_; j <= phase_ && undone; ++j) {extension_ = j;undone = extend( cstr+extension_, phase_-extension_ );}}putEnd(); }template <class CharT, class T> typename SuffixTree<CharT,T>::NodeT* SuffixTree<CharT,T>:: jumpDown(CharT const* str, int len, NodeT* node, bool fromFront) {dbg("# jumping down path len=%d str=\"", len);dbg_puts(str,len);dbg("\" from node %08x ... \n", node);int i=0;if(fromFront) {if (node!=root_ && str[0]!=node->str[0]) {dbg("!!! cannot find such path !!!\n");throw(std::runtime_error("path not found"));}i = node->len != -1?node->len:phase_ - node->depth;}for(; i<len; ) {NodeIterator itr =std::find_if( node->branches.begin(),node->branches.end(),typename NodeT::MatchFirst(str[i]) );if(itr == node->branches.end()) {dbg("!!! cannot find such path !!!\n");throw(std::runtime_error("path not found"));} else {dbg("> going into node %08x which begins with \'%c\', len=%d,"" depth=%d\n",*itr, (*itr)->str[0], (*itr)->len, (*itr)->depth );node = *itr;if( node->len != -1 ) // internal nodei += node->len;else // leafi += phase_ - node->depth;}}if( i != len ) { // implicit nodeif(node->len != -1)node->startAt = node->len - (i-len);elsenode->startAt = phase_ - node->depth - (i-len);}dbg("< done.\n");return node; }template <class CharT, class T> typename SuffixTree<CharT,T>::NodeT* SuffixTree<CharT,T>::splitEdge(NodeT* node, CharT const* leafLabel /*len==-1*/) {/*** \* # <-- startAt* \* node** => => => => => => =>** \* \* newInternal* / \* / newLeaf (return value)* node**/dbg("X spliting edge %08x \n", node);NodeT* newLeaf = allocNode();NodeT* newInternal = allocNode();// newInternal->belongTo = node->belongTo;newInternal->startAt = 0;newInternal->len = node->startAt;newInternal->str = node->str;newInternal->parent = node->parent;newInternal->link = root_;newInternal->depth = node->depth;newInternal->branches.push_back(node);newInternal->branches.push_back(newLeaf);*(std::find(newInternal->parent->branches.begin(),newInternal->parent->branches.end(),node)) = newInternal;node->depth += node->startAt;node->str += node->startAt;node->parent = newInternal;if(node->len != -1) {node->len -= node->startAt;}node->startAt = 0;newLeaf->str = leafLabel;newLeaf->depth = node->depth;newLeaf->link = root_;newLeaf->len = -1;newLeaf->parent = newInternal;dbg(" new internal node = %08x ; \t new leaf = %08x\n",newInternal, newLeaf);return newLeaf; }template <class CharT, class T> bool SuffixTree<CharT,T>::extend(CharT const* str, int pos) {dbg("{{{ in phase %d, extension %d;\n", phase_, extension_);dbg(" adding \'%c\' to suffix tree ... \n", str[pos]);int const whichString = strings_.size()-1;int skiped = currentPos_->depth;NodeT *node = jumpDown(str+skiped, pos-skiped, currentPos_, true);if (node->startAt != 0) { // implicit nodedbg(" got implicit node %08x starts at %d\n", node, node->startAt);if(node->str[node->startAt] != str[pos]) {NodeT *newLeaf = splitEdge( node, str+pos );newLeaf->leafNum = extension_;newLeaf->belongTo=whichString;node = newLeaf->parent;if(latestInternalNode_) {latestInternalNode_->link = node;dbg("-> creating suffix link from %08x to %08x\n",latestInternalNode_,node);}latestInternalNode_ = node;currentPos_ = node->parent;leaves_.push_back(newLeaf);++nLeaves_;} else {dbg(" suffix already exists.\n}}} done.\n");node->startAt = 0;return false; // suffix already exists, all done.}} else { // explicit nodedbg(" got explicit node\n");if(latestInternalNode_) {latestInternalNode_->link = node;dbg("-> creating suffix link from %08x to %08x\n",latestInternalNode_,node);}latestInternalNode_ = node;if( std::find_if( node->branches.begin(),node->branches.end(),typename NodeT::MatchFirst(str[pos]) )!= node->branches.end()) {dbg(" suffix already exists.\n}}} done.\n");currentPos_ = node;return false; // all done.} else if(node->branches.empty() && node!=root_) {// a leaf created in the past, now it should be exdended.node->belongTo=whichString;node->str = str+pos-node->len;node->len = -1;currentPos_ = node->parent;node->leafNum = extension_;leaves_.push_back(node);++nLeaves_;} else {// add a leaf to existing explicit node.NodeT *newLeaf = allocNode();dbg(" adding new leaf %08x to node %08x.\n", newLeaf, node);newLeaf->parent = node;newLeaf->link = root_;newLeaf->str = str+pos;newLeaf->len = -1; // leafnewLeaf->belongTo=whichString;newLeaf->depth = node->depth + node->len;node->branches.push_back(newLeaf);currentPos_ = node;newLeaf->leafNum = extension_;leaves_.push_back(newLeaf);++nLeaves_;}}dbg("-> following suffix link from %08x to %08x ...\n",currentPos_,currentPos_->link );currentPos_ = currentPos_->link;dbg("}}} done.\n");return true; }static inline char* x08 (char* buf, void const * ptr) {sprintf(buf, "%08x", ptr);return buf; }template <class CharT, class T> static void __printSuffixTreeNode(Node<CharT,T>* node,int margin_left,int padding_left,std::basic_ostream<CharT> * stream) {int i,I;char addr[16];if( node->branches.empty()) {for(i=0; i<margin_left; ++i)*stream<<' ';*stream << '\"';for(i=0; i<node->len; ++i)*stream<< node->str[i];*stream << "\" " << x08(addr, node)<< "[" << addr << "] ";*stream << "\n";} else {for(i=0; i<margin_left; ++i)*stream<<' ';*stream << '\"';for(i=0; i<node->len; ++i)*stream<< node->str[i];*stream << "\" " << x08(addr, node)<< "[" << addr << "] ";*stream << ": {\n";for(i=0, I=node->branches.size(); i<I; ++i) {__printSuffixTreeNode(node->branches[i],margin_left+padding_left,padding_left, stream);}for(i=0; i<margin_left; ++i)*stream<<' ';*stream << "} \n";} }template <class CharT, class T> void SuffixTree<CharT,T>::print(std::basic_ostream<CharT> * stream) {assert(!"function not supported"); }template <> void SuffixTree<char,void*>::print(std::ostream * stream) // || // std::basic_ostream<char> {*stream<<"Root ";__printSuffixTreeNode<char,void*>(root_, 0,2, stream); }template <class T> static void __dotPrintNode(Node<char,T>const*node,std::ostream*stream) {char buf[16];int i,I,j;for(i=0,I=node->branches.size(); i<I; ++i) {Node<char,T> const* p = node->branches[i];*stream<<"node"<<x08(buf,p)<<" [label=\"\"";if(p->branches.empty())*stream<<" peripheries=2 width=0.1 height=0.1";*stream<<"];\nnode"<<x08(buf,node);*stream<<" -> node"<<x08(buf,p)<<" [label=\"";for(j=0;j<p->len;++j)if(p->str[j])*stream<<p->str[j];else*stream<<"$";*stream<<"\"];\n";__dotPrintNode(p,stream);}if(!node->branches.empty()) {*stream<<"node"<<x08(buf,node);*stream<<" -> node"<<x08(buf, (node->link))<<" "<<"[color=red];\n";} }template <class CharT, class T> void SuffixTree<CharT,T>::dot(std::basic_ostream<CharT> *) {assert(!"function not supported"); }template <> void SuffixTree<char,void*>::dot(std::ostream * stream) {char buf[16];*stream<<"digraph stree {\n";*stream<<"node"<<x08(buf, root_)<<" [label=\"root\"];\n";*stream<<"node"<<buf<<" -> node"<<buf<<";\n";*stream<<"node [width=0.2 height=0.2] \n";__dotPrintNode<void*>(root_, stream);*stream<<"}\n"; }#endif /* SUFFIXTREE_H */// vi:ts=4:foldmethod=marker7???References
| [1] | : Esko Ukkonen, Suffix tree and suffix array techniques for pattern analysis in strings, Erice School 30 Oct 2005 |
| [2] | (1,?2,?3,?4)?: Gusfield, Dan (1999) [1997]. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press. ISBN 0-521-58519-8 |
| [3] | (1,?2)?: E. Ukkonen, On-Line Construction of Suffix Trees, Algorithmica, 14 (1995), 249-260 |
轉(zhuǎn)載于:https://www.cnblogs.com/sandy2013/p/3260009.html
總結(jié)
以上是生活随笔為你收集整理的suffix tree的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： python中中括号中的负数
- 下一篇： hdu 4679 树状dp