后缀数组（SA）学习笔记

SuperSupper / 2024-08-05 / 原文

~~为什么不叫前缀数组呢~~

常用数组

$sa_i (suffix~array)$ 指字符串 $s$ 中，排名为 $i$ 的后缀从哪一位开始

$rk_i (rank)$ 指字符串 $s$ 从第 $i$ 位开始的后缀在所有后缀中的排名

$h_i (height)$ 指字符串 $s$ 中，从第 $i$ 位开始的后缀与排名为 $rk_{i} - 1$ 的后缀的最长公共前缀

求解方法

对于 $sa$ 和 $rk$ 数组经常一起求解，解这两个数组通常使用倍增方法求。

首先预处理出以每个后缀第一个字符进行排序的 $sa$ 和 $rk$ 数组

接下来进行倍增

将 $sa_i$ 和 $sa_{i + d}$ 接起来
排序
计算 $rk$ 数组

模拟运行过程：

具体实现时排序可以使用计数排序，为了稳定性，将第二关键字倒序加入即可

时间复杂度：$O(n \log n)$

模板：洛谷 P3809

Code

#include <algorithm>
#include <iostream>
#include <numeric>

using namespace std;

const int kN = 1e6 + 1;

int n, sa[kN], rk[2 * kN];
string s;

void I() {
  int b[kN], c[kN];
  fill(b, b + kN, 0);
  iota(sa + 1, sa + n + 1, 1);
  sort(sa + 1, sa + n + 1, [](int x, int y) { return s[x] < s[y]; });
  for (int i = 1; i <= n; i++) {
    rk[sa[i]] = rk[sa[i - 1]] + (s[sa[i]] != s[sa[i - 1]]);
  }
  for (int d = 1; d < n; d <<= 1) {
    for (int i = 1; i <= d; i++) {
      b[i] = n - d + i;
    }
    for (int i = 1, m = d; i <= n; i++) {
      (sa[i] > d) && (b[++m] = sa[i] - d);
    }
    fill(c, c + kN, 0);
    for (int i = 1; i <= n; i++) {
      c[rk[i]]++;
    }
    for (int i = 1; i <= n; i++) {
      c[i] += c[i - 1];
    }
    for (int i = n; i >= 1; i--) {
      sa[c[rk[b[i]]]--] = b[i];
    }
    for (int i = 1; i <= n; i++) {
      int t = rk[sa[i]] != rk[sa[i - 1]] || rk[sa[i] + d] != rk[sa[i - 1] + d];
      b[sa[i]] = b[sa[i - 1]] + t;
    }
    copy(b + 1, b + n + 1, rk + 1);
  }
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> s, n = s.size(), s = 's' + s;
  I();
  for (int i = 1; i <= n; i++) {
    cout << sa[i] << ' ';
  }
  return 0;
}

对 $h$ 数组的求解

如果你注意力惊人的话，可以注意到 $h_{rk_i} \geq h_{rk_{i - 1}} - 1$

注意力不够的话看这里

我也不会证：）

oi-wiki 上的证明

然后可以写出 $O(n)$ 的代码计算

for (int i = 1, x = 0; i <= n; i++) {
  int j = sa[rk[i] - 1];
  for (x = max(0, x - 1); max(i, j) + x <= n && s[i + x] == s[j + x]; x++) {
  }
  h[i] = x;
}

模板：P10469 后缀数组

Code

#include <algorithm>
#include <iostream>
#include <numeric>
#include <set>

using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

const int kN = 1e6 + 1;

int n, a[kN], f[kN], h[kN], sz[kN], mx[kN], sa[kN], rk[kN];
set<int> st;
pll ans[kN];
string s;

void I() {
  int b[kN], c[kN];
  fill(b, b + kN, 0);
  iota(sa + 1, sa + n + 1, 1);
  sort(sa + 1, sa + n + 1, [](int x, int y) { return s[x] < s[y]; });
  for (int i = 1; i <= n; i++) {
    rk[sa[i]] = rk[sa[i - 1]] + (s[sa[i]] != s[sa[i - 1]]);
  }
  for (int d = 1; d < n; d <<= 1) {
    for (int i = 1; i <= d; i++) {
      b[i] = n - d + i;
    }
    for (int i = 1, m = d; i <= n; i++) {
      (sa[i] > d) && (b[++m] = sa[i] - d);
    }
    fill(c, c + kN, 0);
    for (int i = 1; i <= n; i++) {
      c[rk[i]]++;
    }
    for (int i = 1; i <= n; i++) {
      c[i] += c[i - 1];
    }
    for (int i = n; i >= 1; i--) {
      sa[c[rk[b[i]]]--] = b[i];
    }
    for (int i = 1; i <= n; i++) {
      int t = rk[sa[i]] != rk[sa[i - 1]] || rk[sa[i] + d] != rk[sa[i - 1] + d];
      b[sa[i]] = b[sa[i - 1]] + t;
    }
    copy(b + 1, b + n + 1, rk + 1);
  }
}

int F(int x) {
  return f[x] == x ? f[x] : F(f[x]);
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> s, n = s.size(), s = 's' + s;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  I();

  for (int i = 1, x = 0; i <= n; i++) {
    int j = sa[rk[i] - 1];
    for (x = max(0, x - 1); max(i, j) + x <= n && s[i + x] == s[j + x]; x++) {
    }
    h[rk[i]] = x;
  }
  for (int  i = 1; i <= n; i++) {
    cout << sa[i] - 1 << ' ';
  }
  cout << '\n';
  for (int i = 1; i <= n; i++) {
    cout <<  h[i] << ' ';
  }
  return 0;
}

练习：

P2178 [NOI2015] 品酒大会

给定一个字符串 s，若 $lcp(suffix_i, suffix_j) \geq r$，则称 $i$ 和 $j$ 为 $r$ 相似。对于每一个 $0 \le r \le n - 1$，求满足条件的 $(i, j)$ 的数量以及 $a_i * a_j$ 的最大值

$n \le 3 * 10^4, |a_i| \le 10^9$

Solution

对于每一个满足条件的数对，我们将 $i$ 向 $j$ 连边，用并查集处理即可，注意要维护每个块的大小、最大值以及最小值（因为又负数）

但是还会超时，发现倒着枚举 $r$ 只有连边操作，于是倒着枚举，并根据 $h$ 从大到小排序

Code

作者太懒了：（

P8023 [ONTAK2015] Tasowanie

给定两个数字串 $A$ 和 $B$，通过将 $A$ 和 $B$ 进行二路归并得到一个新的数字串 $T$，请找到字典序最小的 $T$。

$n \le 3 * 10^5, m \le 3 * 10^5$

Solution

直接把第二个串接在第一个串后面跑一边后缀数组贪心归并即可，注意两个串的串尾都要放入无穷大的分隔符

Code

``` #include #include #include

using namespace std;

const int kN = 1e6 + 1;

int n, m, _n, _m, s[kN], sa[kN], rk[2 * kN];

void I() {
int b[kN], c[kN];
fill(b, b + kN, 0);
cin >> n, _n = n;
for (int i = 1; i <= n; i++) {
cin >> s[i];
}
s[++n] = 1e9;
cin >> m, _m = m;
for (int i = n + 1; i <= n + m; i++) {
cin >> s[i];
}
n += m;
s[++n] = 1e9;
iota(sa + 1, sa + n + 1, 1);
sort(sa + 1, sa + n + 1, [](int x, int y) { return s[x] < s[y]; });
for (int i = 1; i <= n; i++) {
rk[sa[i]] = rk[sa[i - 1]] + (s[sa[i]] != s[sa[i - 1]]);
}
for (int d = 1; d < n; d <<= 1) {
for (int i = 1; i <= d; i++) {
b[i] = n - d + i;
}
for (int i = 1, m = d; i <= n; i++) {
(sa[i] > d) && (b[++m] = sa[i] - d);
}
fill(c, c + kN, 0);
for (int i = 1; i <= n; i++) {
c[rk[i]]++;
}
for (int i = 1; i <= n; i++) {
c[i] += c[i - 1];
}
for (int i = n; i >= 1; i--) {
sa[c[rk[b[i]]]--] = b[i];
}
for (int i = 1; i <= n; i++) {
int t = rk[sa[i]] != rk[sa[i - 1]] || rk[sa[i] + d] != rk[sa[i - 1] + d];
b[sa[i]] = b[sa[i - 1]] + t;
}
copy(b + 1, b + n + 1, rk + 1);
}
}

int main() {
cin.tie(0)->sync_with_stdio(0);
I();
for (int i = 1, j = _n + 2; i <= _n || j <= _n + _m + 1;) {
if (i <= _n && (rk[i] < rk[j] || j > _n + _m + 1)) {
cout << s[i++] << ' ';
} else {
cout << s[j++] << ' ';
}
}
return 0;
}

</details>

[P1117 [NOI2016] 优秀的拆分](https://www.luogu.com.cn/problem/P1117)

给定一个字符串 s，求 AABB 式的字串数量，其中 A、B 为 S 非空子串

<details>
<summary>Solution</summary>

还在维修：）

</details>

<details>
<summary>Code</summary>

还在维修：）

</details>