好久之前就打算写了，结果咕到现在
倍增求 SA
考虑使用类似计数排序的思想来求 SA，对每个位置 \(i\) 有双关键字 \((rk[i],rk[i+w])\) 优先按照第一关键字排序
char s[np];
int n,id[np * 2],bac[np];
int height[np];
int rk[np * 2],sa[np * 2],oldrk[np * 2];
// rk[i] 表示后缀 i 的排名，sa[i] 表示排名为 i 的后缀是谁
// oldrk[i] 表示上一轮 rk
inline void getsa()
{
int alp=max(256,n);
for(int i=1;i <= n;i ++) bac[rk[i] = s[i]] ++;
for(int i=1;i <= alp;i ++) bac[i] += bac[i-1];
for(int i=n;i >= 1;i --) sa[bac[rk[i]]--] = i;
for(int w=1;w < n;w <<= 1) // (i,i+2^w)]
{
for(int i=0;i <= alp; i++) bac[i] = 0,id[i] = i;
for(int i=1;i <= n;i ++) bac[rk[id[i] + w]] ++;//排第二关键字
for(int i=1;i <= alp;i++) bac[i] += bac[i-1];
for(int i=n;i >= 1;i --) sa[bac[rk[id[i] + w]]--] = id[i];
for(int i=0;i <= alp;i ++) bac[i] = 0,id[i] = sa[i];// 按照上一维的排名排第一维
for(int i=1;i <= n;i ++) bac[rk[id[i]]] ++;
for(int i=1;i <= alp;i ++) bac[i] += bac[i-1];
for(int i=n;i >= 1;i --) sa[bac[rk[id[i]]]--] = id[i];
for(int i=1;i <= n;i ++) oldrk[i] = rk[i];
for(int i=1,p=0;i <= n;i ++)
{
if(oldrk[sa[i]] == oldrk[sa[i - 1]] && oldrk[sa[i] + w] == oldrk[sa[i-1] + w])
rk[sa[i]] = p;// 本质相同
else rk[sa[i]] = ++p;//
}
}
}
求 height 数组
规定：
\(\operatorname{height}_i\) 表示 \(i-1\) 和 \(i\) 的两后缀的最长公共前缀
\(h_i\) 表示后缀 i 和排名在 i 之前一位的后缀最长公共前缀
直接给出结论
如何求 \(\operatorname{height}\) 数组呢
再给出结论 \(h_i \geq h_{i-1}-1\)
给出证明
对于 \(h_i = \operatorname{lcp}(i,sa_{rk_i-1})\)
设 \(u = i,v = sa_{rk_i-1}\)
对于 \(h_{i-1}\) 来说，设 \(u' = i-1,v' = sa_{rk_{i-1}-1}\)
不妨设 \(k=h_{i-1}\geq 1\) 对于另一部分结论显然成立
则有 \(\operatorname{lcp}(u',v')=k\)，考虑去掉 \(u'\) 与 \(v'\) 的首字母后分别为 \(x\) 与 \(y\)，且有 \(x\) 与 \(y\) 的字典序相对大小不变。显然有 \(\operatorname{lcp}(x,y)=k-1\) 并且 \(x=u=i\)。相当于 \(\operatorname{lcp}(i,y)=k-1\)。
最后有如下关系 \(y\leq v < i\) 根据 LCP lemma 有 \(\operatorname{lcp}(v,i)\geq \operatorname{lcp}(y,i)\)
证毕
这条性质可以被称作「不完美单调性」
inline void getHeight()
{
for(int i=1,k=0;i <= n ;i ++)
{
if(rk[i] == 1) height[1] = 0;
else{
if(k > 0) k --;
int l=sa[rk[i] - 1];
while(l + n <= n && i + k <= n && s[i + k] == s[l + k]) k ++;
height[rk[i]] = k;
}
}
}
CF1063F
显然有一个 \(O(n\sqrt n)\) 的优雅做法，但我们要追求 \(\rm polylog\) 做法
考虑一个dp
设 dp[i] 表示起始是 i 的最大划分数量。则有这样一个转移
或者
现在我们手里有了一个 \(O(n^2)\) 的 dp 考虑优化
经过推理可以发现一个性质 \(dp[i] \leq dp[i+1] + 1\)
可以观察出这个东西非常像 \(\rm height\) 的数组形式，我们考虑和它类似的维护
每次都直接继承上一个答案，然后顺序递减枚举即可。
考虑如何 check 当前 dp 值是否合法
相当于 dp 值需要同时满足 min 中的三个表达式
对于 \(\operatorname{lcp}(s[i+1:n],s[j:n])\) 只需要在对应的 \(sa\) 区间上二分左右端点就行。
对于前两个条件，只需要保证在当前 dp 值下降的时候维护一棵线段树不断向其中插入元素即可，同时维护 dp 最大值。
P4094
sa 套路题之一吧算是。
首先二分答案
考虑如何 check 是否存在 \(\max\limits_{i=a}^b\operatorname{lcp}(s[i:b],s[c:d]) \geq ans\) 即可
首先对 sa 建主席树，每次 check 直接在 c 在 sa 的位置上二分左右区间，然后做一个二维数点就行
sa 经典题了算是
P4770
首先有一个和上题一模一样的做法不过复杂度是 \(O(\sum|T|\log^2n)\)
考虑优化，发现对于 \(T[i-1]\) 和 \(T[i]\) 它们必然有这样一个关系
考虑和 \(h_i\) 一样的证明即可，对于不完全单调性可以使用一个类似 CF1063F 的做法，这样复杂度就被降到 \(O(\sum|T|\log n)\) 了
但是由于每次都要在主席树上查询和二分实在是太慢了，并且数组访问并不连续。