国家集训队2004论文集许智磊.ppt

后缀数组——定义和符号 后缀数组——定义和符号 后缀数组——定义和符号 后缀数组——构造方法 后缀数组——构造方法 后缀数组——构造方法 后缀数组——构造方法 后缀数组——构造方法 后缀数组——构造方法 后缀数组——构造方法 后缀数组——构造方法 后缀数组——构造方法 后缀数组——构造方法 后缀数组——构造方法 后缀数组——方法总结 后缀数组——辅助工具 后缀数组——辅助工具 后缀数组——辅助工具 后缀数组——辅助工具 后缀数组——辅助工具 后缀数组——辅助工具 后缀数组——辅助工具 后缀数组——应用举例 后缀数组——应用举例 后缀数组——应用举例 后缀数组——应用举例 后缀数组——应用举例 后缀数组——应用举例 后缀数组——应用举例 后缀数组——应用举例 后缀数组——应用举例 后缀数组——应用举例 后缀数组 VS 后缀树 后缀数组 VS 后缀树 后缀数组 VS 后缀树 后缀数组 VS 后缀树 后缀数组——最后的话 后缀数组 后缀数组——关于“$” 后缀数组——关于“$” 后缀数组——关于“$” 后缀数组——关于“$” 后缀数组——关于“$” 后缀数组——关于“$” 后缀数组——关于“$” 后缀数组——关于“#” 后缀数组——关于“#” 后缀数组——关于“#” 后缀数组——关于线性算法 后缀数组——关于线性算法 后缀数组——关于线性算法 后缀数组——关于线性算法 后缀数组——关于线性算法 后缀数组——关于线性算法 后缀数组——关于线性算法 后缀数组——关于空间 后缀数组——关于空间 后缀数组——关于空间 后缀数组——关于RMQ 后缀数组——关于RMQ 后缀数组——关于倍增思想 后缀数组——关于倍增思想 后缀数组——关于倍增思想 后缀数组——关于倍增思想 后缀数组——关于倍增思想 $ 中心 i i=2m-i+2 i-r i+r i+r # 求以i为中心向两边扩展的最远值，等价于 求Suffix(i)和Suffix(i)的最长公共前缀 后缀数组！！！ 同时和粉红串反射相等 T串 T串 Suffix(i)和Suffix(i)的公共前缀 解法： 初始化答案为0。按照前述方法修改串T，得到串S 求出后缀数组SA、名次数组Rank 计算height数组并进行标准RMQ方法预处理 复杂度：　　设len(S)=n，则n=2m+2 O(m) + O(nlogn) + m*O(1) = O(nlogn) 枚举i，计算以i为中心向两边扩展的最远值并更新答案 + 2*O(n) 后缀树也可以做到类似的事情 后缀数组有什么优势呢？ 后缀数组在信息学竞赛中最大的优势： 易于理解，易于编程，易于调试 后缀数组比后缀树占用的空间少 ——处理长字符串，如DNA分析 时间复杂度的比较 按照字符总数|Σ|把字符集Σ分为三种类型： Constant Alphabet —— |Σ|是一个常数 Integer Alphabet —— |Σ|为字符串长度n的多项式函数 General Alphabet —— 对|Σ|没有任何限制 Constant Alphabet　　Integer Alphabet　　General Alphabet 后缀数组是直接针对General Alphabet设计的算法 复杂度跟字符集的类型没有关系 后缀树则对不同字符集有不同的表现 如果采用儿子-兄弟方式来表达后缀树： 构造的复杂度为O(n*|Σ|) ——显然不适合Integer和General Alphabet， 对于|Σ|稍大的Constant Alphabet也无法胜任 解决方法：每个节点建立一棵红黑树来保存儿子，复杂度为O(n*log|Σ|)。　 ——竞赛的时候有时间编吗？ 结论 对于Integer和General以及|Σ|较大的Constant Alphabet，后缀树甚至在时间复杂度上都无法胜过后缀数组。 但是对于|Σ|较小的Constant Alphabet， 后缀树还是有着速度上的优势的。 ——我们要根据实际情况，因“题”制宜选择合适的数据结构 研究后缀数组，不是因为害怕后缀树的繁琐 也没有贬低后缀树，抬高后缀数组的意思 对于功能相似的两个数据结构，我们应该灵活地掌握，有比较有选择地使用 构造后缀数组用到的倍增思想对我们的思考也是有帮助的 为什么规定S以“$”结尾？ 设u=Suffix(i)，v=Suffix(j) 后缀u，以i开头 后缀v，以i开头 对u、v在2k-前缀意义下进行比较 k k k k 比较红色字符相当于在k-前缀意义下比较Suffix(i) 和 Suffix(j) 比较绿色字符相当于在k-前缀意义下比较Suffix(i+k) 和 Suffix(j+k) 在2k-前缀意义下比较两个后缀可以转化成 在k-前缀意义下比较两个后缀 i+k j+k 2k