后缀数组\(SA\)
后缀数组，维护的是原字符串的每一个后缀，将其按照字典序大小排序，得到一些有用的信息。
首先明确几个数组的定义：
sa[] //sa[i] 表示字典序第 i 小的后缀在原串中的起始位置为 sa[i]
rk[] //rk[i] 表示原串从 i 位置开始的后缀的字典序的排名
h[] //h[i] 表示排名为第 i 的后缀与排名为第 i-1 的后缀的最长公共前缀
接下来我们考虑每个数组要怎么求解。
求解 \(rk\)
对于 \(rk\) 数组我们考虑倍增法求解，我们从长度为 \(1\) 开始，每次将长度翻倍，得到新的长度中的排名。
具体的，对于每一个位置 \(j\) ，已经求解了长度为 \(i\)，准备求解 长度为 \(2i\) 的。也就是说我们当前已经求解出了 \(s[j-(j+i-1)]\) 和 \(s[(j+i)-(j+2i-1)]\) 这两个字符串的排名，根据字典序的定义，优先比较靠前的串，因此我们将前一个串的排名设为 \(j\) 这个位置的第一关键字，将第二个串的排名设为 \(j\) 这个位置的第二关键字，然后进行双关键字基数排序 ( 可以用 \(sort\) ) 但是复杂度会多一个 \(log\) ，排完序后就可以得到 \(s[j-(j+2i-1)]\) 这个串的排名。不断进行倍增，就可以求出每个后缀的排名了。
特别的，对于 \(j+i > n\) 的，我们直接将 \(0\) 设为 \(j\) 位置的第二关键字即可。
求解 \(sa\)
求完 \(rk\) 之后，根据定义来看，求 \(sa\) 就是一行的事。
sa[rk[i]]=i
求解 \(h\)
\(h\) 数组在 \(sa\) 的题目中相当常见，对于 \(h\) 有两条关键的性质。
- 排名为 \(i\) 的后缀与排名为 \(j\) 的后缀的最长公共前缀 \(=min_{i=l+1}^rh_i\)
- $h(rk_i) \geq h(rk_{i-1})-1 $
第一条性质的正确性是显然的。
我们重点来关注第二条。
我们设 \(k=sa[rk[i-1]-1]\) ，即 \(h(rk_{i-1})=Lcp(k,i-1)\)
- 若 \(h(rk_{i-1}) \leq 1\) ，结论显然成立
- 若 \(h(rk_{i-1}) > 1\) ，此时 \(Lcp(k,i-1) >1\)，我们把两个串的首位丢掉，也就是 \(i\) 和 \(k+1\) 这两个串，因此 \(Lcp(k+1,i)=Lcp(k,i-1)-1\)。由于 \(k\) 排在 \(i-1\) 前面，因此 \(k+1\) 也排在 \(i\) 前面，根据第一条性质，我们可以得到 \(min_{i=rk[k]+1}^{rk[i]}h_i=h(rk_i-1)-1\) ，所以 \(h(rk_i)\geq h(rk_{i-1})-1\)。得证。
根据第二条性质，我们可以按照 \(rk\) 数组的顺序，从小到大依次求解 \(h(rk_1)\)、\(h(rk_2)\)、……. \(h(rk_n)\)，每次答案至少是上一次的答案 \(-1\)，因此就可以在 \(o(n)\) 的复杂度内求解。
`int flag=0,rk[N],sa[N],h[N],fi[N],se[N],b[N],g[N],tp[155];
inline void Round(int *a) {
int mx=0;
for(int i=1;i<=n;i++) mx=max(mx,a[i]);
for(int i=0;i<=mx;i++) b[i]=0;
for(int i=1;i<=n;i++) b[a[i]]++;
for(int i=1;i<=mx;i++) b[i]+=b[i-1];
for(int i=n;i>=1;i–) rk[g[i]]=b[a[g[i]]]–;
for(int i=1;i<=n;i++) g[rk[i]]=i;
}
inline void Qsort() {
int idx=1;
for(int i=1;i<=n;i++) rk[i]=g[i]=i;
Round(se); Round(fi);
for(int i=2;i<=n;i++)
rk[g[i]]=(fi[g[i]]fi[g[i-1]] && se[g[i]]se[g[i-1]])?rk[g[i-1]]:++idx;
if(idx==n) flag=1;
}
inline void Getsa() {
mem(tp); for(int i=1;i<=n;i++) tp[s[i]-‘a’]=1;
for(int i=1;i<155;i++) tp[i]+=tp[i-1];
for(int i=1;i<=n;i++) rk[i]=tp[s[i]-‘a’];
for(int i=1;i<=n && !flag;i<<=1) {
for(int j=1;j<=n;j++)
fi[j]=rk[j], se[j]=j+i>n?0:rk[j+i];
Qsort();
}
for(int i=1;i<=n;i++) sa[rk[i]]=i;
}
inline void Geth() {
int k=0;
for(int i=1,j;i<=n;i++) {
if(k) –k;
j=sa[rk[i]-1];
while(s[i+k]==s[j+k] && s[i+k]!=’|’) k++;
h[rk[i]]=k;
}
}`
板子是根据自己的理解写出来的，比较屑，常数也比较大。
一些经典的套路、例题
P2178 [NOI2015] 品酒大会
对于这一类的题目，可以对于 \(h\) 数组从大到小排序，然后依次将 \(h_i\) 表示的串用并查集连接起来，用并查集维护信息。
[NOI2016] 优秀的拆分
对于这一类，求解与连续重复 \(k\) 次的字符串相关的题目，都可以考虑通过设置关键点的方法，做到在调和级数的复杂度之内求解。
具体的
我们从小到大枚举循环节的长度 \(L\) ，然后依次枚举所有的关键点：\(L\) 、\(2L\) 、……. \(kL\)。
假设当前枚举到了关键点 \(i\) ,我们处理所有的满足左端点在区间 \((i-L,i]\) 之内的，循环次数大于等于 \(2\) 的串的贡献。
我们设 \(A=Lsp(i,i+L)\)，\(B=Lcp(i,i+L)\)。
首先为了限制左端点的位置，我们令 \(A=min(A,L)\)。
于是我们考虑的这些串中最大循环次数为 \(k=\left\lfloor \frac{A+B-1}{L} \right\rfloor +1\)，这样的串共有 \(z=min(A,(A+B-1)\mod L+1)\) 个。
最后再单独考虑循环次数为 \(1\) 的串的贡献(这样可以减少分类讨论的难度)。
这种方法既可以用于求最值，也可以用来求方案数，时间复杂度 \(o(n\ln n)\)。
P4248 [AHOI2013]差异
统计每一个子串作为 \(Lcp\) 的次数，可以在 \(h\) 数组上面跑单调栈。
P4070 [SDOI2016]生成魔咒
动态维护 \(h\) 数组，答案为字符串的本质不同子串个数。\(ans=\frac{n(n+1)}{2}-\sum_{i=1}^nh_i\)。
其余，待更…….
原文地址：http://www.cnblogs.com/oscaryangzj/p/16845333.html
