---

---

補充一下 suffix tree 的說明好了
大部分人應該是沒看過這東西
他是一種 tree（廢話）
根據輸入的字串來建立一個 suffix tree
這個 tree 的每個分支都代表這個字串的一個 suffix

suffix 就是詞尾，後置修飾
舉例來說 programmer 這個單字，er 就是他的一個 suffix，因為 programmer
gra 則不是 programmer 的 suffix

一個長度 n 的字串有 n 個 suffix
以字串 cocoa 來說
他的五個 suffix 分別是

        cocoa
        ocoa
        coa
        oa
        a

suffix tree 就是根據一個字串的 suffix 建立的 tree
例如上面那個 cocoa 可以表示成

        root
        ├ a                    //     a
        ├ co
        │ ├ a                 //   coa
        │ └ coa               // cocoa
        └ o
           ├ a                 //    oa
           └ coa               //  ocoa

suffix tree 可以提供我們 pattern matching 的功能
例如我們如果要尋找 cocoa 裡面有沒有 oco 這個子字串
只要沿著 suffix tree 從 root 慢慢往下走就可以
時間複雜度是子字串的長度，相當不錯！
傳統 pattern matching 在長度 n 的母字串搜索長度 m 的子字串
時間複雜度分別有 O(mn), O(n), O(n/m) 不過 worst case 也是 O(mn) 等演算法

如果利用 suffix tree 來搜索子字串，每次只需要付出 O(m) 的成本，
當你需要在一個超大母字串裡面搜索很多種子字串的時候，
例如你想知道一個檔案裡面是不是含有病毒，
就可以把這個檔案建成 suffix tree，
然後把你已經知道的數千種病毒特徵拿下去比對，（當然這個例子簡化了很多）
這種時候 suffix tree 就很合用。

建立 suffix tree 最差的方法當然就是暴力法，
你第一次取出整個字串，放到 tree 裡面去，
從 root 開始比對，如果都一樣就繼續往下走，
如果遇到不一樣的字元，那就可以分支，並且完成這次插入，
第二次取出後面 n-1，然後比對跟分支，
第三次取出後面 n-2...
....
總共 n 次，時間複雜度 O(n^2)

天哪！O(n^2)！那根本就很慢阿！
不過好險 suffix tree 存在 O(n) 的建構法，
很複雜，不太容易用 BBS 說明 XD
幸好網路上有很詳細的教學
http://www.cise.ufl.edu/~sahni/dsaaj/enrich/c16/suffix.htm
http://wwwmayr.in.tum.de/konferenzen/Ferienakademie99/maass/applet.html
suffix tree 除了 pattern matching 以外還有很多其他的用途
像是資料壓縮，Longest common squence，或是其他點點點點

現在大家都知道 suffix tree 是幹什麼吃的了
考慮下面這個字串
aj;fej$@#afFap,k3258akaqehhvlleqhf
很亂，對，
這表示每次我在加入一個新的 suffix 到 tree 裡面的時候
都會因為 char squence 的不同，比沒兩個字元就很快分支，然後完成插入

但是如果我的字串長這樣
1234567812345678123456781234567812345678123456781234567812345678
瞎子已經看出來他每八個字元循環一次了
當然我插入前面八個 suffix 的時候還沒有問題
問題是當我要插入第九個的時候，
他會跟第一個一直 match，一直 match，都無法分支
一直到最後最後把整個字串都跑完了，才發現不同（一個是字元結束，一個是1）
這就是為什麼循環的字串會讓整個程式的速度突然 down 下來

要不是靈光一閃
我可能永遠以為我的程式有錯 T_T

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.129.180

--
Shaken, Not Stirred.
--
※ 作者: TL 時間: 2013-01-27 18:41:10