曾经看过许XX的论文 不过没有看懂
09年罗XX的论文比那篇容易理解的多
后缀数组果然是一个很强大的东西 有关字符串的问题 只要学好自动机和后缀数组基本都能解决了
与其说是后缀数组强大 不如说height数组强大 后缀数组的作用也就是方便求解height数组
使用height数组 大致有如下你个常用方法
1、分组:将height值大于等于k的分置一组 使得同组内最长公共前缀>=k
2、二分:根据具体情况 一般都是二分答案
3、连接：将所有涉及到的字符串连在一起处理
还有一个神奇的性质:当循环节长度确定时 保证覆盖是s[0],s[l],s[l*2]～～中的某连续两个
posted on 2009-04-14 12:29
250 阅读(3288)
评论(2) 编辑 收藏 引用 所属分类:
oi