后缀数组小结②

【cxjyxx_me是个大沙茶 他连后缀数组这个pj算法都不会。。】
h[i]      表示sa[i]和sa[i – 1]的最长公共前缀

O(n^2)的朴素就很傻×了
但是按lsq的话说  这 样 做 并 没 有 利 用 字 符 串 的 性 质 。
可以证明(论文里。。)
h[i] >= h[i – 1] – 1
所以只要按0~n-1的顺序求h值就可以达到O(n)的时间出解
void get_h(int n)
{
  for (int i = 0; i < n; ++i) rank[sa[i]] = i;
  for (int i = 0, k = 0; i < n; h[rank[i++]] = k)
  if (rank[i])
    for (k = k ? k – 1 : 0; s[i + k] == s[sa[rank[i] – 1] + k]; ++k);
  else k = 0;
}

h[i]      表示sa[i]和sa[i – 1]的最长公共前缀
rank[i] 表示第i个后缀的rank值
这个代码貌似就没什么好解释的了了。。
就是比lsq的代码多判了一个rank
因为的的sa下标是从0开始、
————————————
另附一个预处理方法
o(nlogn)的预处理 可以在O(1)查询任意两个后缀的最长公共前缀
dp[i][j]  表示从h[i]开始的1<<j个h值的min
这个可以nlogn求出来

然后要求h[l]~h[r]的最小值时
设k为floor(log_2(r – l))
最小值为min(dp[l][k], dp[r – (1 << k)][k])
这只是思路 具体下标好像有点不一样、、
———————应用———————-
这些基本就是概述下论文里的应用了。。

最长公共前缀
min(h[rank[l]+1]~h[rank[r]])
可重叠最长重复子串
h数组max值
不可重叠最长重复子串
二分长度 可以用mid把h数组分成好几块
如果在一块中出现两个坐标绝对值>=mid则返回true
可重叠的最长重复k次子串
     二分长度 分块后如果有一块元素个数>=k个则返回true
不相同的子串的个数
按rank值从小到大循环后缀
考虑一个后缀对不同子串的贡献是len-h[i]
最长回文子串
把s翻转后接接在s串后面 中间要加一个没出现过的字符作为分隔
考虑以第i个字符为中心的回文串长度即为后缀i和后缀len-i的最长公共前缀
奇数偶数都要考虑
奇偶使用的后缀是不一样的
连续重复子串
枚举长度为i 考虑后缀0和后缀i的最长公共前缀 可以在预处理后O(1)判断是否合法
重复次数最多的连续重复子串
枚举这个子串的长度为L
那么这个子串必定包含0, L*1, L* 2, …, L*m
枚举这几个位置
求出 L * i 和 L*(i + 1)  的最长公共前缀和最长公共后缀
设长度为k 则重复了k/L+1次 更新ans

2串最长公共子串
把第二个串接到第一个串后面 并在中间加入一个没出现的分隔符
求出sa和h后
枚举第一个串的每一位
如果sa[rank[i] + 1]是第二个串的后缀 则可以用h[rank[i + 1]]更新答案
如果sa[rank[i] – 1]是第二个串的后缀 则可以用h[rank[i ]]更新答案

长度不小于 k 的公共子串的个数
这个也是用h数组乱搞一下就行了 由于我对这题的定义不是很理解 就不写了。。
不小于 k 个字符串中的最长子串
对于多字符串问题 一般的处理方法是把所有字符串连接起来并每两个间用不一样的字符隔开
二分长度 对h分块 如果一块中出现k个字符串则返回true
每个字符串至少出现两次且不重叠的最长子串
二分长度 如果一块对每个字符串都出现了坐标绝对值>=mid的两个后缀 则返回true

出现或反转后出现在每个字符串中的最长子串
二分长度 如果一块对每个字符串都出现了后缀或反转后的后缀 则返回true
————————————————
终于写完了=、=。。 还有写的一些题目 放在后几篇吧- -‘

发表评论