后缀、Border的研究-学习笔记

by jcvb # 性质 ### 字符串 u, v 满足 2|u| ≥ |v|, 则 u 在 v 中的所有匹配位置组成一个等差数列。  ### 字符串 s 的所有不小于 |s|/2 的 border 长度组成一个等差数列 证明: 设 s 的最大 border 长度为 n − p, (p ≤ |s|/2), 另外某个border 的长度为 n − q, (q ≤ |s|/2), 则 gcd(p, q) 是 s 的周期, 即n − gcd(p, q) 是 s 的 border 长度, 于是 gcd(p, q) ≥ p ⇒ p | q。 自己悟出来的： 如果串s的border$> |s|/2$，那么这个border的循环节也是大串的循环节。 # 应用 ## 子串所有border（等差数列表示） 若 |u| = |v|, 记 PS(u, v) = {k : pre(u, k) = suf(v, k)} 记 LargePS(u, v) = {k ∈ PS(u, v) : k ≥ |u|/2} 我们按border的长度分类为$[2^i,2^{i+1})$，最后一段不足也没关系。   长度为2的整次幂的子串的出现位置（字典序排名）正好是后缀排序的过程！我们记录下来即可。  空间$O(n\log n)$，预处理$O(n\log n)$，每次询问$O(\log^2n)$，瓶颈在IPM的询问是$O(\log n)$的。 可以优化到每次询问$O(\log n)$：  $[i,i+|v|]$会被长度为$|v|$的区间分成两部分，我们在两部分的等差数列里分别查一下即可。 ## 子串最小border CF1043G $O(\sqrt{N})$找： 1.对于$\le \sqrt{N}$的border暴力找。 2.对于$>\sqrt{N}$的border： 那么$l$和$r-border+1$这两个后缀在后缀数组上的排名$\le \sqrt{N}$ 如果$>$，那么这个串的出现肯定会重叠，也就说明这个串有更小的border。 ## 子串最大border [BJWC2018]Border 的四种求法 ## 子串最小后缀 法一： 设$p=\arg\min_{i\in[l,r]}(s[i..n])$ 则答案为p的最小border 法二： 记$f(l,r)$为$[l,r]$的答案，则有 $$f(l,r)=\min(s[p..r],f(r-2^k+1,r))$$ 其中$2^k\le r-l+1<2^{k+1}$ 原因是有border的串的最小border一定$\le len/2$ 于是可以预处理后$O(1)$查询。 ## 子串最大后缀 求一个 p, 使得maxsuf(l, r) = max {s[p..r], maxsuf(r − m + 1, r)} 成立。 设 maxsuf(l, r) = s[x...r]。只需考虑 l ≤ x < r − m + 1 的情形,即需要求出 x。   证明： 为什么$q|p_2-x$？否则，串$s[x..r]$会有一个比q更小的周期$w=\gcd(q,p_2-x)$，那么$p_2$应该$=p_1-w$，否则，可以画图，然后根据$s[r+1..n]<s[r+1-q..n]$证明$p_1-w$更优。而且感性的理解也很奇怪，你说为啥$p_2\neq p_1-w$，而是一个奇奇怪怪的$p_2=p_1-kw$？ 最后，显然真正的最长公共后缀一定是周期q不断往前延伸，否则反证法可以得到矛盾。