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