后缀数组(SA) 学习笔记

2023-03-22 · 算法

天梯赛校赛碰到的本以为切个水题没想到捅了老挝

甚至还有n,q=10w的区间众数 2333 就是数据比较水感觉严一点分块都不一定能过

原题貌似是这个但是他妈的校赛n改到了2w

一开始感觉是差分+lcs或kmp之类的然后感觉不太对劲...

还是需要一些处理字符串的手段于是学一下SA和SAM 已经拖了挺久了...

前面的定义和求解过程理解移步oi-wiki即可

那上面有图解，看的更清楚

定义

对于一长为 $n$ 的字符串 $s$ 即 $s[1-n]$ 令 $suf[i]=s[i-n]$ 称为后缀 $i$

将 $s$ 的 $n$ 个后缀排序

$sa[i]$ 表示第 $i$ 小的后缀的编号即 $suf[sa[i]]$ 是第 $i$ 小的后缀
$rk[i]$ 表示后缀 $i$ 的排名

即 $sa[rk[i]]==rk[sa[i]]=i$

求后缀数组

$O(n^2logn)$ 求法很显然。直接暴力排序就行了

考虑两个连续长为1的子串即 $s[i]$ 和 $s[i+1]$ 的排名 $rk_0[i]$ 和 $rk_0[i+1]$ 作为两个关键字

能够得到所有长为2的子串的 $sa_1[i]$ 通过 $sa_1[i]$ 得到 $rk_1[i]$ 然后再求 $sa_2[i]$

以此类推得到 $sa_w[i]$ 表示子串 $s[i\to i+2^w-1]$ 的后缀数组

整个过程就是用 $s[i\to i+2^j-1]$ 的子串排名即 $rk$ 数组去求解 $s[i\to i+2^{j+1}-1]$ 的子串的后缀数组 $sa$

能够倍增的原因就是因为连续的字符串排字典序前面优先级大于后面折半做就很显然

当 $2^w\geq n$ 时即为整个串的后缀数组

#include <bits/stdc++.h>
using namespace std;
int main() {
  string s;
  cin >> s;
  int n = s.size();
  s = '$' + s;
  vector<int> sa(n + 1), rk(n + 1 << 1), ork(n + 1 << 1);
  for (int i = 1; i <= n; ++i)
    sa[i] = i, rk[i] = s[i];
  for (int w = 1; w < n; w <<= 1) {
    sort(sa.begin() + 1, sa.end(), [&](int x, int y) {
      return rk[x] == rk[y] ? rk[x + w] < rk[y + w] : rk[x] < rk[y];
    });
    ork = rk;
    for (int p = 0, i = 1; i <= n; ++i)
      if (ork[sa[i]] == ork[sa[i - 1]] && ork[sa[i] + w] == ork[sa[i - 1] + w])
        rk[sa[i]] = p;
      else
        rk[sa[i]] = ++p;
  }
  for (int i = 1; i <= n; ++i)
    cout << sa[i] << " \n"[i == n];
  return 0;
}

倍增+sort 中间还有个更新操作就是 $O(nlogn+n)=O(nlogn)$ 的复杂度

呃呃然后按理说 $O(nlog_nlog_n)$ 是过不去的但是C++17开了O2居然就直接过了... 过了...

submission

但是语言与时俱进的同时丧心病狂的出题人肯定也会与时俱进所以我们还是要学习标准算法的 233

复杂度降到 $O(NlogN)$

计数排序和基数排序 OI-wiki随便看下就好了没有什么难度

如何快速理解计数排序？

某种意义上可以当成桶排来理解

const int N = 100010;
const int W = 100010;

int n, w, a[N], cnt[W], b[N];

void counting_sort() {
    memset(cnt, 0, sizeof(cnt));
    for (int i = 1; i <= n; ++i) ++cnt[a[i]];
    for (int i = 1; i <= w; ++i) cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; --i) b[cnt[a[i]]--] = a[i];
}

如何快速理解基数排序？

多关键字排序，每个关键字可以选择一个合适的方法（一般是计数排序）排完之后保证稳定性，然后排下一个关键字

基于计数排序实现的基数排序可以理解成桶排的桶排

基于这个理念，我们依赖O(n)的辅助存储空间代替sort的比较

#include <bits/stdc++.h>
using namespace std;
int main() {
  string s;
  cin >> s;
  int n = s.size();
  s = '$' + s;
  int m = 127;
  vector<int> sa(n + 1), rk((n + 1) << 1), cnt(m + 1);
  for (int i = 1; i <= n; ++i)
    ++cnt[rk[i] = s[i]];
  for (int i = 1; i <= m; ++i)
    cnt[i] += cnt[i - 1];
  for (int i = n; i >= 1; --i)
    sa[cnt[rk[i]]--] = i;
  auto _rk = rk;
  for (int p = 0, i = 1; i <= n; ++i)
    if (_rk[sa[i]] == _rk[sa[i - 1]])
      rk[sa[i]] = p;
    else
      rk[sa[i]] = ++p;
  m = n;
  cnt.resize(m + 1);
  for (int w = 1; w < n; w <<= 1) {
    fill(cnt.begin(), cnt.end(), 0);
    auto _sa = sa;
    for (int i = 1; i <= n; ++i)
      ++cnt[rk[_sa[i] + w]];
    for (int i = 1; i <= m; ++i)
      cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; --i)
      sa[cnt[rk[_sa[i] + w]]--] = _sa[i];

    fill(cnt.begin(), cnt.end(), 0);
    _sa = sa;
    for (int i = 1; i <= n; ++i)
      ++cnt[rk[_sa[i]]];
    for (int i = 1; i <= m; ++i)
      cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; --i)
      sa[cnt[rk[_sa[i]]]--] = _sa[i];
    
    _rk = rk;
    for (int p = 0, i = 1; i <= n; ++i)
      if (_rk[sa[i]] == _rk[sa[i - 1]] && _rk[sa[i] + w] == _rk[sa[i - 1] + w])
        rk[sa[i]] = p;
      else
        rk[sa[i]] = ++p;
  }
  for (int i = 1; i <= n; ++i)
    cout << sa[i] << " \n"[i == n];
  return 0;
}

OI-wiki上还有一些常数优化内容我懒得研究了ToT..

然后就是看 SA-IS 和 DC3

定义

求后缀数组

复杂度降到 O(NlogN)O(NlogN)

复杂度降到 $O(NlogN)$