果然\(SA\)这种东西是精益求精。
梳理一下大致思路。
以下思路中\(prefix[x]\)代表桶的前缀和，其余不变。
目的是得到所有\(suf_x\)的排序。在这里考虑倍增玩法。
先把所有的\(suf_x\)按照\(suf_x\)的\(ss[1]\)扔到桶里，对桶做前缀和。
对于拥有相同的\(ss[1]\)的\(suf_x\)，显然在他们的\(rank\)至少是\(prefix[x[1]]\)
第一次对\(suf_x\)排序，大小为1，直接对\(x\)正着扫一遍，得到\(rank\)以后在桶的对应位置减掉。
现在有了第一轮排序的\(rank\)和\(SA\)
开始考虑倍增。
实际上就是合并长度为\(len\)的作为第一关键字的\(suf_x\)和作为第二关的\(suf_{x+len}\)
现在有\(n\)个位置等你排序，作为关键字的\(suf\)长度是\(siz\)
发现从\(n - siz + 1\)这个位置开始，第二关键字都是空的
因此就得到排名为\(i\)的第二关键字 所属的第一关键字位置
现在考虑除了第二关键字为空的\(suf\)之外可以充当第二关键字的\(suf\)
发现如果一个\(suf\)所在的位置\(i>siz\)，那么这个位置对应的第一关键字位置就是\(i-siz\)
因为获取第二关键字位置是递增的，于是可以扫\(SA\)，同时判断\(SA_i\)位置来判断这个位置是否纳入第二关键字
现在获取了所有第二关键字及其对应第一关键字的位置。
当前所拥有的\(x\)实际上是上次排序后的，也就是仅仅以第一关键字为排名所得到的每个\(suf_x\)的排名。
然后扫\(y_i\)，把对应\(x_i\)扔到桶里，然后对桶求前缀和
接着刷新\(SA\)，但是不能直接考虑\(SA_i\)因为压根就求不出来
尝试用\(y_i\)来看看对\(SA\)的影响。
联系一下预处理时对\(prefix\)的操作，发现取得的排名是越来越小的，
也就是说，对于上一次排序拥有相同排名的第一关键字，应该倒着取第二关键字，以正确造成对桶对应位置的影响
所以得到了\(SA[c[x[y[i]]]--]=y[i]\)
我们正确刷新了\(SA\)，接着再来刷新\(rank\)。
很明显\(x_i\)也不能直接求，但是可以通过互相映射的已经刷新的\(SA\)来取得对应关系。
同时手头还有第二关键字。
对于排名相等的\(SA_i\)与\(SA_{i-1}\)再比较第二关键字
因为要直接取得位置为\(SA_i\)的第二关键字，所以就是\(SA_i+siz\)直接使用第一关键字比较即可
如果相同那么获得相同排名，否则取得更大的排名。
对于每次刷新完以后，会有较多重复排名，因此可以通过每次刷新排名后最大排名\(p\)来更新桶的上界\(m\)
如果有\(n\)个不同排名或达到上界即停止排序。
取得的是每个位置\(x\)的\(rank\)和每个\(rank\)的位置\(x\)，所以上文称互为映射。
定义 \(LCP(i,j)\)为\(suf(SA[i])\)和\(suf(SA[j])\)的最长公共前缀
对于一个\(suf(SA[i]),\)显然有\(suf(SA[i-1])\)或者是\(suf(SA[i+1])\)
使得其是使\(suf(SA[i])\)有最长\(LCP\)的可匹配\(suf\)
在\(i<j<k\)情况下首先有\(LCP(i,j)\geq LCP(i,k)\)
现在有若干\(LCP\)相关结论
1 : 固定\(i,k\)且\(i<k,j\in(i,k)\)时 \(LCP(i,k)=min_{j\in(i,k)}\lbrace{LCP(i,j),LCP(j,k)}\rbrace\)
证明
定义 \(p = min_{j\in(i,k)}\lbrace{LCP(i,j),LCP(j,k)}\rbrace\),
\(q1 = suf(SA[i]), q2 = suf(SA[j]), q3 = suf(SA[k])\)
此时\(q1\)和\(q2\),\(q2\)和\(q3\)的前\(p\)个字符相等,所以有\(LCP(i,j)\geq p\)
那么\(LCP(i,j) \geq p, LCP(j,k) \geq p\),并且\(q1[p + 1] \neq q2[p+1]\)或\(q2[p+1]\neq q3[p + 1]\)
但是如果满足了\(q1[p+1]=q3[p+1]\)且不满足上面两个条件中至少一个,就与\(SA\)的性质矛盾
所以得到\(LCP(i,j)\leq p\) , 综上所述\(LCP(i,j)=p\)
其实也可以用\(LCP Base\)理解 因为要满足\(\forall j\in(i,k) ,LCP(i,j)\geq LCP(i,k)\)
所以\(LCP = min_{j\in(i,k)}\lbrace{LCP(i,j),LCP(j,k)}\rbrace\)
2 : \(LCP(i,k) = min_{j\in[i,k)}\lbrace{LCP(j,j+1)}\rbrace\)
证明 ：
可以利用\(LCP Lemma\) 拆成\(LCP(i,k) = min_{j\in(i,k)}\lbrace{LCP(i,i+1),LCP(i+1,k)}\rbrace\)的递归形式。
定义\(Height[i] = LCP(i, i - 1);i = 1\)时明显有\(Height[1] = 0,\)\(suf(i)\)的排名为\(rk[i]\)
从\(LCP\space Theorem\)可以知道\(LCP(i,k) = min_{j\in(i,k]}{Height[j]}\)
定义\(h[i] = Height[rk[i]]\)
现在有结论 ： \(h[i] \geq h[i - 1] - 1\)
如果排在\(suf(i-1)\)前一个的是\(suf(k)\)，
那分别删除首字符后就得到了\(suf(i)\)和\(suf(k+1)\)
因为\(suf(k)\)本身排在\(suf(i-1)\)前面，同时删除首字符以后一定还是排在前面
当然如果首字符不匹配，那么式子一定成立。
\(suf(k)\)实际上是\(suf(SA[rk[i-1]-1])\)，所以\(LCP\)即为\(h[i-1]\)
同时删除首字符后得到的\(LCP(k+1,i)=h[i-1]-1\)
因为\(suf(k+1)\)一定排在\(suf(i)\)的前面，所以也一定包含了\(suf(SA[rk[i]-1])\)
又因为\(SA[rk[i]-1]\geq SA[rk[k+1]]\)
从而由\(LCP Base\)可以知道\(h[i]\geq h[i-1]-1\)
原文：https://www.cnblogs.com/cjc030205/p/11638100.html