補充一下 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