后缀排序
本文做复习用，不宜初学用。
定义
\(sa\) 表示排名为 \(i\) 的位置。
\(rk\) 表示位置为 \(i\) 的排名。
\(y\) 表示按照第二关键字排序排名为 \(i\) 的位置。
\(height\) 表示排名为 \(i\) 和 \(i - 1\) 的后缀的最大前缀
\(h\) 表示位置为 \(i\) 和它排名前一位的后缀的最大前缀
操作流程
最初字符串排序
这里是桶排序基础操作。
for(int i = 1; i <= n; ++i) ++c[rk[i] = a[i]];
for(int i = 1; i <= m; ++i) c[i] += c[i - 1];
for(int i = n; i >= 1; ++i) sa[c[rk[i]--] = i;//按照1,2,3的顺序排
为什么是倒叙的呢？你用手模拟一下ababa这个样例就懂了
进行倍增比较操作。
for(int i = 1; i <= n; i <<= 1)
第二关键字排序
这里是把最后那一部分没有第二关键字的放在最前面。
num = 0;
for(int i = n - k + 1; i <= n; ++i) y[++num] = i;
对有第二关键字的排序。按照 \(sa\) 数组，也就是排名进行。
for(int i = 1; i <= n; ++i) if(sa[i] - k > 0) y[++num] = sa[i] - k;
总体排序
清空桶。
for(int i = 1; i <= m; ++i) c[i] = 0;
这里先按照 \(rk\) 排序，和最初字符串排序有点类似。
for(int i = 1; i <= n; ++i) ++c[rk[i]];
for(int i = 1; i <= m; ++i) c[i] += c[i - 1];
for(int i = n; i >= 1; --i) sa[c[rk[y[i]--] = y[i];//按照y[i]的顺序排
更新 \(rk\) 数组和 \(m\)
这里把 \(y\) 和 \(rk\) 交换其实就是用 \(y\) 暂时存储上一次的 \(rk\) 。
比较当前 \(sa[i]\) 和 \(sa[i - 1]\) 是否完全相等。如果相等就和 \(sa[i-1]\) 赋一样的 \(num\)
swap(rk,y);num = 0;
for(int i = 1; i <= n; ++i)
rk[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && sa[i] + k <= n && sa[i - 1] + k <= n && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++num;
if(num == n) break;
m = num; num;
LCP
定义
\(suff(i)\) 表示以 i 开头的后缀。
\(height[i]\) 表示排名为 \(i\) 与排名为 \(i-1\) 的后缀字符串的前缀。
\(h[i]\) 表示位置为 \(i\) 与它的排名\(-1\) 的后缀字符串的前缀。
形式化的：
\[height[i] = lcp(suff(sa[i]),suff(sa[i - 1]))\\
h[i] = height[rk[i]],height[i] = h[sa[i]]
\]
有这样的好性质：
\[h[i] \ge h[i - 1] - 1 \\
lcp(suff(i),suff(j)) = \min_{x = rk[i] + 1} ^ {rk[j]}lcp(suff(sa[x]),suff(sa[x - 1]))
= \min_{x = rk[i] + 1} ^ {rk[j]} height[x]
\]
所以要算 \(lcp\) 直接用一个 \(RMQ\) 就可以了。
求 h 数组
这里很好理解。
for(int i = 1; i <= n; ++i){
h[i] = h[i - 1] - 1;
if(h[i] < 0) h[i] = 0;
while(a[sa[rk[i]] + h[i]] == a[sa[rk[i] - 1] + h[i]] ) ++h[i];
}