GsT通用后缀树( Generalized) 对于长度为n的字符串建立后缀树, WINDOWS INDIGOS 1234567 1234567 直接的方法时间复杂度为o(n*n) 1973年 Weiner提出线性时间算法 ·1976年 Mccreigh提出更节约内存 的算法 1995年 Ukkonen提出线性时间建 树算法 123)(L,4) 8只岛。 北大物些 有,轴即叠究 帖·有,轨盘即彭究 单词粒度的后缀树 后缀树的应用 “ I know you know$” ■查找字符串中的子串 ■统计S中出现T的次数 ■找出S中最长的重复子串 出现了两次以上的子串 know 两个字符串的公共子串 最长共同前缀(LcP) 回文串 北京大学值歌张写所有即究 后缀树的应用 后缀数组 ■中文切词 字符串S的后缀数组SA 关联分析 发现经常共同出现的短语 对s的所有后缀的指针排序 ■频繁模式挖掘 即后缀树叶结点的字典序 STC聚类 m后缀树ST=后缀数组SA+ ■基因/蛋白序列对比/分类 LcP数组4 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 19 z 对于长度为n的字符串建立后缀树， 直接的方法时间复杂度为O（n*n） z 1973年Weiner提出线性时间算法 z 1976年McCreigh提出更节约内存 的算法 z 1995年Ukkonen提出线性时间建 树算法 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 20 GST——通用后缀树(Generalized) $ O ND W I $OG D $OGI OW$ $OG ND $OGI OW$ $OGI OW$ $W $ INDOW$ $ (2, 3) (1, 4) (2, 5) (2, 4) (2, 1) (1, 2) (2, 2) (1, 3) (1, 5) (2, 6) (1, 6) (1, 1) (1, 7) (2, 7) WINDOW$ INDIGO$ 1234567 1234567 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 21 单词粒度的后缀树 z “I know you know $ ” 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 22 后缀树的应用 „ 查找字符串中的子串 „ 统计S中出现T的次数 „ 找出S中最长的重复子串 „ 出现了两次以上的子串 „ 两个字符串的公共子串 „ 最长共同前缀(LCP) „ 回文串 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 23 后缀树的应用 „ 中文切词 „ 关联分析 „ 发现经常共同出现的短语 „ 频繁模式挖掘 „ STC 聚类 „ 基因/蛋白序列对比/分类 „ …… 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 24 后缀数组 „ 字符串S的后缀数组SA „ 对S的所有后缀的指针排序 „ 即后缀树叶结点的字典序 „ 后缀树ST = 后缀数组SA + LCP数组