后缀数组(SA)

jiazhaopeng · 2019-12-08 14:02:05 · 个人记录

SA 的用处（经典题型）：

求LCP，LCS，本质不同子串数
出现 xxx 次子串，字符串中不重叠地出现至少两次的最长串长度
最长AA式子串，连续的若干相同子串（AABB式）

首先说一下，本篇博客是本人在oi-wiki学习后缀数组是写下的笔记，更详细的证明等见oi-wiki_SA

后缀数组主要包含两个数组：sa[ ] 和 rk[ ]。

$rk[i]$表示 $i$ 后缀的字典序排名。 ## 求后缀数组 - 模板提交处：[P3809 【模板】后缀排序 (SA)](https://www.luogu.com.cn/problem/P3809) 其中倍增求 $SA$ 的代码如下（使用基数排序）： ```cpp #include <iostream> #include <algorithm> #include <cmath> #include <cstdio> #include <cstring> #include <string> #define N 2000010 template<typename T> inline void read(T &x) { x = 0; char c = getchar(); bool flag = false; while (isdigit(c)) {if (c == '-') flag = true; c = getchar(); } while (isdigit(c)) {x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); } if (flag) x = -x; } using namespace std; char s[N]; int sa[N], rk[N], oldrk[N], id[N], p, n, w, limi; int bin[N]; int main() { scanf("%s", s + 1); n = strlen(s + 1); for (register int i = 1; i <= n; ++i) ++bin[rk[i] = s[i]]; for (register int i = 1; i <= 300; ++i) bin[i] += bin[i - 1]; for (register int i = n; i > 0; --i) sa[bin[rk[i]]--] = i; limi = 300;//注意是limi不是p，因为for一开始时不会执行limi = p for (w = 1; w < n; w <<= 1, limi = p) { //处理id p = 0; //注意p = 0 for (register int i = n; i > n - w; --i) id[++p] = i;//注意"i" for (register int i = 1; i <= n; ++i) if (sa[i] > w) id[++p] = sa[i] - w;//注意"sa[i] - w" 注意"sa[i]" //处理sa memset(bin, 0, sizeof(bin)); for (register int i = 1; i <= n; ++i) ++bin[rk[id[i]]]; for (register int i = 1; i <= limi; ++i) bin[i] += bin[i - 1]; for (register int i = n; i > 0; --i) sa[bin[rk[id[i]]]--] = id[i]; //处理rk（去重） memcpy(oldrk, rk, sizeof(rk)); p = 0; //注意p = 0 for (register int i = 1; i <= n; ++i)//注意"i - 1" 注意"oldrk" rk[sa[i]] = (oldrk[sa[i]] == oldrk[sa[i - 1]] && oldrk[sa[i] + w] == oldrk[sa[i - 1] + w]) ? p : ++p; //注意 + w if (p == n) break;//小优化:如果已经排好序了，就不用再排了。 } for (register int i = 1; i <= n; ++i) printf("%d ", sa[i]); return 0; } ``` 例题： [字符加密](https://www.luogu.com.cn/problem/P4051) ## 后缀数组的height数组 $height[i]$ 表示 $sa[i]$ 后缀和 $sa[i - 1]$ 后缀的 $lcp$ （最长公共前缀）。 ### 求height数组我们发现一个规律： $height[rk[i]] >= height[rk[i - 1]] - 1

证明感性加玄学（详见oi-wiki_SA）：

假设i - 1的height为5，那么

```cpp for (register int i = 1, k = 0; i <= n; ++i) { if (k) k--;//height[rk[i]] >= height[rk[i - 1]] - 1; while(s[i + k] == s[sa[rk[i] - 1] + k]) ++k; height[rk[i]] = k; } ``` 至于为什么是 $O(n)$ 是因为可以证明 $k--$ 的次数是有限的，最多 $n$ 次，所以最多加 $2n$ 次。 ## 应用 ### 求两子串的最长公共前缀 - 题意简述：给定一小写字母组成的字符串，形如 $abababcabcabc$，规定 $s[l][r]$ 为$l~r$间的子串，如 $s[2][5] = baba$ 。多次询问，每次给出两组 $l$,$r$，求各自 $lcp$。 $len <= 100000, 1 <= l <= r <= len

分析与解

首先要知道，lcp(sa[i], sa[j]) = min(height[i...j])，感性证明一下，就是从 i 到 j 都没变，那就是他们的 lcp 了。

这样，我们已知 lcp(i, j)， lcp(l...r, l'..r') 就用子串长度和 lcp(i, j) 取最小者即可。

通过ST表，可以把复杂度降为 O(nlogn +q)。

比较子串的字典序大小

求完后缀数组后，我们能 O(1) 地比较两后缀的大小，现在要比较子串大小，只需把 lcp(A,B) >= min(|A|, |B|) 的情况特判掉即可。

有 sa,rk,height 数组后过于简单，故不赘述。

求本质不同的子串数

我们按所有后缀以字典序从大到小的顺序考虑。子串数就是后缀的前缀数，这个好求，关键是求出多算的那些相同的子串数。

排序后第 i 名串与第 i - 1 名串的重叠部分长度为 lcp(sa[i], sa[i - 1])，这里多算了 lcp(sa[i], sa[i - 1]) 个子串，把他们减去即可。

至于只考虑相邻后缀的正确性，据说可以用 lcp(sa[i], sa[j]) = min(height[i...j]) 来证明。

long long ans = (n * (n + 1)) >> 1;
for (register int i = 2; i <= n; ++i) {
    ans -= height[i];//height[i] = lcp(sa[i], sa[i - 1]);
}

求一个子串的字典序排名

例如，我们求 ABABABD 中 BABA 的字典序排名。

我们可以先求出SA和height数组，然后查询 BABA 所在的后缀 BABABD。然后之前的后缀的前缀字典序一定比它小。因此直接统计一下本质不同的子串数量(len - height)，再加上B,BA,BAB 比它小，就好了。

不过有时候BABABD后缀的 height 可能比4大，这意味着前面所有 BABA... 的串的字典序都比 BABA 大。因此我们直接二分找到最靠下的第一个不包含 BABA 的后缀，这及之前的那些子串一定比 BABA 小，再加上 B,BA,BAB 即可。

求出现至少 k 次的最长子串长度

经典例题：牛奶模式

题意简述

给定一字符串，求出现至少 k 次的最长子串长度。

len <= 20000

分析与解

把子串转换为后缀的前缀，如果有几个相同的子串，那么在排序后的后缀中应该为相邻的一部分，且它们的 lcp 一定大于等于子串长度。所以出现至少出现 k 次的最长子串长度一定是在排序后连续至少 k 个的 lcp 的最大值。然后就变成滑动窗口，用单调队列维护即可。

当然，既然求 SA 都到达了 O(nlogn)，那么二分答案的那个 log 也不算什么了。

### 字符串中不重叠地出现至少两次的最长串长度注意到答案具有单调性，故考虑二分。二分长度 $len$，对于排序后的后缀，找到 $lcp$ $>=$ $len$ 的连续的几段，它们一定出现了至少两次，且长度大于等于 $len$。现在要判断有没有不重叠的两个子串。我们贪心地找出每段中最靠前的那个子串和最靠后的那个子串，如果这两个都重叠，那就不可行，缩小 $len$，否则扩大 $len$。 #### 加强版：不重叠出现至少k次的最长串长度对于这种**不重叠**问题，较为常见的方法是**根据子串在原串中的位置来判断**。同样二分答案，将同一块内所有子串的编号（位置）排个序，然后又知道了串长，可以知道子串的起始位置和终止位置。然后就相当于“选择最多不交线段”的问题了，可以贪心解决。复杂度 $O(nlog^2n)$，但是第二个 $log$ 非常小。有个 $O(nlogn)$ 的做法：我们把同一个块内的所有子串**在原字符串中打上标记**，然后**在原串上扫描一遍**，贪心选取每种串即可。这样是稳定 $O(nlogn)$ 的。例题：[4097. 【GDOI2015】短信加密](https://gmoj.net/senior/#main/show/4097) ### 最长AA式子串 - [T121316 最长重复子串](https://www.luogu.com.cn/problem/T121316) 枚举len，每len个点放一个点，则重复子串一定跨越两个点。对于相邻点对，求lcp和lcs，判断。 [my record](https://www.luogu.com.cn/record/30999613) ### AABB式的子串个数看一下例题吧：[优秀的拆分](https://www.luogu.com.cn/problem/P1117) 题解的图非常好：[题解【P1117优秀的拆分】](https://www.cnblogs.com/acfunction/p/10087144.html) 这里给出关键部分代码： ```cpp int array[N];//array[i]:从i开始向右延伸的"AA"个数 int dearray[N];//dearray[i]:从i开始向左延伸的"AA"的个数 inline void calc(int pos, int len) { int lcp = A.get_lcp(pos + 1, pos + len + 1); if (lcp > len - 1) lcp = len - 1; int lcs = B.get_lcp(n - (pos + len) + 1, n - pos + 1); if (lcs > len) lcs = len; if (lcs + lcp < len) return ; int chonghe = lcs + lcp - len; array[pos - lcs + 1]++; array[pos - lcs + 2 + chonghe]--; dearray[pos + len + lcp - chonghe]++; dearray[pos + len + lcp + 1]--; } ... for (register int i = 1; i <= (n >> 1); ++i) { for (register int j = i; j + i <= n; j += i) { calc(j, i); } } ``` 还是看图理解吧。 ### AxxxA式（xxx的个数已知）的子串个数 - [UVA10829 L-Gap Substrings](https://www.luogu.com.cn/problem/UVA10829) 照样和前两种模型的解决方法类似：枚举A串的长度 $len$，每 $len$ 个字符中放一个点。我们的任务是查询第一个A（长度为len）包含某一个点的AxxxA式的串有多少个。设当前点为$l$，则令$r = l + g + len$，其中 $g$ 表示给定的 $x$ 的个数，并求出其lcp，lcs（与len取min）然后就要自己动手画图了。推出该AxxxA串的左端点的区间为 $[l - lcs + 1, l + lcp - 1 - len + 1]$，即 $[l - lcs + 1, l + lcp - len]$，这样的话合法的xxx的个数为 $lcp + lcs - len$。记得答案对0取max（非负）。 [my record](https://www.luogu.com.cn/record/33949534) ### 结合各种数据结构 - 结合并查集典型例题：[品酒大会](https://www.luogu.com.cn/problem/P2178) 不说了，满眼都是泪。 $Code$: [my record](https://www.luogu.com.cn/record/32152957) - 结合单调栈通常用来求一个字符串中相同子串对数。例题：[差异](https://www.luogu.com.cn/problem/P4248)， [找相同字符](https://www.luogu.com.cn/problem/P3181) ## 需要注意的地方 - 注意什么时候用 $rk$,什么时候用 $s$。把 $rk$,$sa$,$s$ 分清楚，SA这块的调错就问题不大了。 - 如果有多组数据，记得把数组**都**清空一下。需要清空的数组有：$rk,s,sa,height,id,oldrk,bin$;以及$p,w,limi$。总之都清空就问题不大了。 - 注意求 $height$ 时是 $s[i + k] == s[sa[rk[i] - 1] + k]$，注意**不要把-1搞到rk[]里面！！注意是 $sa[rk[i]-1]$ 而不是** * * * * ！！！！ - 求height的最后是```height[rk[i]] = k```!! - 注意 $forforfor$ 中处理 $rk$ 时是 $oldrk[sa[i] + w] == oldrk[sa[i - 1] + w]$，是 **+** ！！！！ - 利用SA求lcp，用st表时，一定要**在height数组上做St表，不能转化到字符上！！** 因为不是求字符间最小值，是求height数组最小值，有些性质字符不符合的！！！不要耍小聪明！！！ ## 小结以下需要记忆 - 求sa，求height - 在基数排序时，$sa$ 一直是一对一的，但不够准确；$rk$ 是多对一的，所以有 $bin[rk[id[i]]]++$，但它是越来越分散的，最后变成一对一。 - $height[rk[i]] <= height[rk[i - 1]] - 1

lcp(sa[i], sa[j]) = min(height[i...j])

附

SA 模板（调试用）

inline void build() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for (register int i = 1; i <= n; ++i)   ++bin[rk[i] = s[i]];
    for (register int i = 1; i <= 300; ++i)   bin[i] += bin[i - 1];
    for (register int i = n; i > 0; --i)    sa[bin[rk[i]]--] = i;
    limi = 300;//注意是limi不是p，因为for一开始时不会执行limi = p
    for (w = 1; w < n; w <<= 1, limi = p) {
        //处理id 
        p = 0;                      //注意p = 0 
        for (register int i = n; i > n - w; --i)    id[++p] = i;//注意"i"
        for (register int i = 1; i <= n; ++i) 
            if (sa[i] > w)  id[++p] = sa[i] - w;//注意"sa[i] - w"   注意"sa[i]"

        //处理sa 
        memset(bin, 0, sizeof(bin));
        for (register int i = 1; i <= n; ++i)   ++bin[rk[id[i]]];
        for (register int i = 1; i <= limi; ++i)    bin[i] += bin[i - 1];
        for (register int i = n; i > 0; --i) sa[bin[rk[id[i]]]--] = id[i];

        //处理rk（去重） 
        memcpy(oldrk, rk, sizeof(rk));
        p = 0;                      //注意p = 0 
        for (register int i = 1; i <= n; ++i)//注意"i - 1"  注意"oldrk" 
            rk[sa[i]] = (oldrk[sa[i]] == oldrk[sa[i - 1]] && oldrk[sa[i] + w] == oldrk[sa[i - 1] + w]) ? p : ++p;
            //注意 + w
    }
    for (register int i = 1, k = 0; i <= n; ++i) {
        if (k)  k--;//height[rk[i]] >= height[rk[i - 1]] - 1;
        while(s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
        height[rk[i]] = k;
        //注意rk
    }
}

st表的构建与lcp的查询模板（调试用）

inline void build_st() {
  for (register int i = 1; i <= n; ++i) f[i][0] = height[i];
  for (register int j = 1; j <= 18; ++j) {
      for (register int i = 1; i <= n; ++i) {
          if (i + (1 << (j - 1)) <= n)
              f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
          else  f[i][j] = 0;
      }
   }
}
inline int query(int l, int r) {
    l = rk[l], r = rk[r];
    if (l > r)  swap(l, r);
    ++l;
    int jibie = Log2[r - l + 1];
    return min(f[l][jibie], f[r - (1 << jibie) + 1][jibie]);
}

记忆方法

rk 问位置返回排名， sa 问排名返回子串位置！！
rk 一开始不是 1~n，到最后才是 1~n！而 sa 无论何时都是 1~n 的！！
每次基排都是以rk为关键字！
for (register int i = 1; i <= n; ++i) if (sa[i] > w) id[++p] = sa[i] - w; （基排第一步） 因为每次是根据后面排前面，所以要按照后面排名的次序枚举，然后把前面加入到id数组里面！！
rk[sa[i]] = (oldrk[sa[i]] == oldrk[sa[i - 1]] && oldrk[sa[i] + w] == oldrk[sa[i - 1] + w]) ? p : ++p; （去重部分，易错点） ①当然是根据 sa 来确定 rk 啦，总不能单用字符位置就确定 rk 吧。 ②一定要和前一名比较！不然就会出现第0名的情况。 ③ 要根据 oldrk 来比较！！不然前面就白干了。不然不觉得 memcpy() 那一步没用吗？不觉得整条语句太短了吗？
while(s[i + k] == s[sa[rk[i] - 1] + k]) ++k; 牢牢记住 s[sa[rk[i] - 1] + k] ！即前一名往后k位的字符!!有了这个不难知道我们是在以下标（位置)的次序求 height!!因此最后为：height[rk[i]] = k; 另外，当 k = 0 的时候，我们其实在比较第1位。因此不用质疑那一个 while()，也不要最后写成 k - 1！此外，虽然 height[1] = 0 是肯定的，但是我们是按照位置的次序求的，因此一开始不要初始化 i 为 2！要初始化为 1！
最后再记一下 w < n。

Updated$ $on$ $Dec.9th