代码
- void rsort() { for (int i = 1; i <= m; ++i) tax[i] = 0;
- for (int i = 1; i <= n; ++i) ++tax[rnk[i]];
- for (int i = 1; i <= m; ++i) tax[i] += tax[i-1];
- for (int i = n; i>= 1; --i) sa[tax[rnk[tmp[i]]]--] = tmp[i];
- }
- void ssort() {
- for (int i = 1; i <= n; ++i) rnk[i] = a[i], tmp[i] = i;
- m = 127;
- rsort();
- for (int w = 1, p = 0; p <n; w <<= 1) {
- p = 0;
- for (int i = 1; i <= w; ++i) tmp[++p] = n - w + i;
- for (int i = 1; i <= n; ++i) if (sa[i]> w) tmp[++p] = sa[i] - w;
- rsort();
- std::swap(rnk, tmp);
- rnk[sa[1]] = p = 1;
- for (int i = 2; i <= n; ++i) {
- rnk[sa[i]] = (tmp[sa[i]] == tmp[sa[i-1]]
- && tmp[sa[i]+w] == tmp[sa[i-1]+w]) ? p : ++p;
- }
- m = p;
- }
- for (int i = 1, k = 0; i <= n; ++i) {
- while (a[i+k] == a[sa[rnk[i]-1]+k]) ++k;
- h[rnk[i]] = k;
- if (k) --k;
- }
- }
应用
关于后缀数组和后缀自动机, 在 hihocoder 上有一套很好的题 (重复旋律).
最长可重叠重复 K 次子串问题
(hiho1403 http://hihocoder.com/problemset/problem/1403 ) h 数组中长度为 k 的子串的最小值的最大值.
最长不可重叠重复子串问题
(hiho1407 http://hihocoder.com/problemset/problem/1407 ) 二分答案为 k, 若 h 数组中有连续的一段大于 k 的值 (即有一个子串重复了), 且这一段中最靠前的位置和最靠后的位置之间的差大于 k(即这个子串可以不重叠), 那么该答案合法.
- bool check(int x) {
- int mn = N + 10, mx = 0;
- for (int i = 1, flag = 0; i <= n; ++i) {
- if (h[i]>= x) {
- if (!flag) { // mark
- mx = std::max(mx, sa[i-1]);
- mn = std::min(mn, sa[i-1]);
- }
- mx = std::max(mx, sa[i]);
- mn = std::min(mn, sa[i]);
- flag = 1;
- } else if (flag) {
- flag = 0;
- if (mx - mn>= x) {
- return true;
- }
- mn = N + 10;
- mx = 0;
- }
- }
- return false;
- }
注意由于 h 数组的定义, 我们需要标记为 mark 的部分.
最长公共子串问题
(hiho1415 http://hihocoder.com/problemset/problem/1415 ) 将两个子串拼接起来, 用'#'分隔, 那么两个串的最长公共子串就是保证 sa[i] 和 sa[i-1] 不在同一个串内的最大的 h[i].
连续重复次数最多的子串
(hiho1419 http://hihocoder.com/problemset/problem/1419 ) 枚举子串长度 l 和重复起点 p, 计算重复次数 lcp(p, p+l)/l + 1, 复杂度 \(O(n^2)\). 考虑优化, 我们可以以 l 的间隔枚举 p, 考虑某个位置 p, 记 lcp(p, p+l) 为 R, 那么, 被我们忽略掉的位置 p-1,p-2,p-3... 的答案值不会超过 R+1. 对于 \(p-R\bmod l <x < p\) 的 \(x\), 以 x 为起点的答案值不可能超过 R(由公式易得), 而对于 \(p-l<x<p-R\bmod l\) 的 \(x\), 以 x 为起点的答案值也不可能超过以 p-R%l 的答案值, 所以只需计算成倍的 p 和 p-R%l 的答案值即可.
- for (int l = 1; l <= n; ++l) {
- for (int i = 1; i+l <= n; i += l) {
- int R = lcp(i, i + l);
- ans = std::max(ans, R / l + 1);
- if (i>= l - R%l) {
- ans = std::max(ans,
- lcp(i - l + R%l, i + R%l) / l + 1);
- }
- }
- }
不同子串的数目问题
\(\frac{1}{2}n(n+1)-\sum_{i=1}^n h[i]\)
[Note] 后缀数组
来源: http://www.bubuko.com/infodetail-2752269.html