SA & SAM
Nygglatho
·
·
个人记录
SA
令 n 表示 s 的长度，t_i 表示 s 的后缀 i（即 s_{n-i+1\sim n} 组成的字符串）。
令 p_i 表示 t_i 经过排序后的结果，则 \mathrm{sa}_i 表示 p_i 的开头在 s 原来 的位置。由于 t_i 开头固定为 n-i+1，所以 \mathrm{sa}_i 是唯一的。
$\mathrm{rk}$ 数组是 $\mathrm{sa}$ 数组的逆运算。即：$\mathrm{sa}(\mathrm{rk}(i))=\mathrm{rk}(\mathrm{sa}(i))=i$。
发现后缀的长度不一样，比较不牛，于是我们在原来 $s$ 的字符串后面加入 $>n$ 个 ASCII 为 $-\infty$ 的字符，这样后缀的排序就变成了固定长度为 $n$ 的排序了。
而 $\text{sa}_i$，此时就是字符串 $s$ 的子串 $[i,i+n]$ 排序后的结果，可以直接 sort + cmp 解决。
但这样是 $O(n^2\log n)$ 的。考虑用倍增（类似归并排序？）的思想优化。
具体地，令 $\text{rk}_x(i)$ 表示子串 $[i,i+2^x]$ 经过排序后的在所有 $2^x$ 长度子串中的排名，考虑已经得到了 $\text{rk}_{x-1}(i)$ 的值，那么根据字典序比较规则，比较子串 $[i,i+2^x]$ 和 $[j,j+2^x]$，先比较 $[i,i+2^{x-1}]$ 和 $[j,j+2^{x-1}]$，可以发现，这个大小值就对应了 $\text{rk}_{x-1}(i)$。如果相同，则再比较 $[i+2^{x-1}+1,i+2^x]$ 和 $[j+2^{x-1}+1,j+2^x]$，对应了 $\text{rk}_{x-1}(i+2^{x-1})$，进行排序即可，时间复杂度 $O(n\log^2n)$，~~开 -O2 可过~~。
```cpp
int main() {
cin >> s;
n = s.size();
s = ' ' + s;
F(i, 1, n) rk[i] = s[i], sa[i] = i;
sort (sa + 1, sa + n + 1, [](int x, int y) {
return rk[x] < rk[y];
});
F(i, 1, n) _rk[i] = rk[i];
for (int i = 1, p = 0; i <= n; ++ i) {
if (_rk[sa[i]] == _rk[sa[i - 1]]) {
rk[sa[i]] = p;
} else {
rk[sa[i]] = ++ p;
}
}
for (w = 1; w < n; w <<= 1) {
sort (sa + 1, sa + n + 1, [](int x, int y) {
if (rk[x] == rk[y]) return rk[x + w] < rk[y + w];
return rk[x] < rk[y];
});
F(i, 1, n) _rk[i] = rk[i];
for (int i = 1, p = 0; i <= n; ++ i) {
if (_rk[sa[i]] == _rk[sa[i - 1]] && _rk[sa[i] + w] == _rk[sa[i - 1] + w]) {//不用真的赋 -inf，因为已经初始化 rk 为 0 了
rk[sa[i]] = p;
} else {
rk[sa[i]] = ++ p;
}
}
}
F(i, 1, n) cout << sa[i] << ' ';
}
```
为了更加简洁，其实最开始并不需要排序。因为 $\text{sa}$ 基于的是 $\text{rk}$ 的相对大小关系，一开始 $\text{rk}(i)$ 直接为 $s_i$ 的 ASCII 即可。
## SAM