非常简洁的后缀数组教程

[guevara]

非常简洁的后缀数组教程



https://ift.tt/Hw5nx7k

定义

\(sa[i]\)：字典序第 \(i\) 小的后缀（suffix array）

\(ra[i]\)：后缀 \(str[i...n]\) 在 \(sa\) 中的下标（rank）

思路

假定字符串长度为 \(n\)，它必然是一个 2 的幂（不足就认为后面是空）

后缀数组 \(sa[i]\) 可认为是长为 \(n\) 的情况下字典序第 \(i\) 小的子串 \(sa_n[i]\)（不足就认为后面是空）

它可以通过长度为 \(n/2\) 的字典序 \(sa_{n/2}[i]\)（以及当前的 \(ra\)）的所有情况来 \(O(1)\) 判断得出

（也就是说对于 \(str[i,i+2^j)\) 可通过 \(str[i,i+2^{j/2})\) 和 \(str[i+2^{j/2},i+2^j)\) 的关键字组合得出）

因此 \(sa[i,n]\) 的集合可通过 \(sa_1[i],sa_2[i],sa_4[i] \dots sa_{n/2}[i]\) 各个集合来倍增递推得出

所以倍增法的最优实现复杂度是 \(O(nlogn)\)

（当前介绍的具体实现是基于快排的 \(O(nlog^2n)\)）

具体过程

举个例子

\[str=ababaaab\] \[n = 8\]

我们认为最小的合法字典序为 0，空子串的字典序为 -1

通过自下而上的先从 \(ra_0[i]\) 算起

其中横坐标代表 \(i\),空使用 \(X\) 来表示

每一次迭代的 \(str\) 是表示 \(str[i,i+2^j)\) 的字串

（比如 \(j=2\) 时的 \(str\) 中从 0 数起第 5 个串表示为 \(aabX\)，即 \(str[5,9)\)）

我们保证不可能存在 \(ra\) 出现第一关键字为 -1 的情况

j = 0
[str] a b a b a a a b
[ra0] 0 1 0 1 0 0 0 1
j = 1

[str] (a,b) (b,a) (a,b) (b,a) (a,a) (a,a) (a,b) (b,X)

[ra0] (0,1) (1,0) (0,1) (1,0) (0,0) (0,0) (0,1) (1,-1)

[ra1]   1     3     1     3     0     0     1     2
j = 2

[str] (ab,ab) (ba,ba) (ab,aa) (ba,aa) (aa,ab) (aa,bX) (ab,XX) (bX,XX)

[ra1]  (1,1)   (3,3)   (1,0)   (3,0)   (0,1)   (0,2)   (1,-1)  (2,-1)

[ra2]   (4)     (7)     (3)     (6)     (0)     (1)     (2)     (5)
j = 3

[str] (abab,aaab) (baba,aabX) (abaa,abX) (baaa,bX) (aaab,X) (aabX,X) (abX,X) (bX,X)

[ra2]    (4,0)       (7,1)       (3,2)      (6,5)   (0,-1)   (1,-1)   (2,-1)  (5,-1)

[ra3]     (4)         (7)         (3)        (6)     (0)      (1)      (2)     (5)

（其实可以看出，当第一关键字互不相同时，已经不需要再多余递推下去了，这种优化策略在大量随机串很大幅度提高效率，比如 \(str = hfkdjfhkjsfhdksja\) 只需计算一遍）

如果需要倍增法最优的实现，可参考国家集训队大佬给出的基数排序版本

也有 \(O(n)\) 实现的SA-IS算法，不过我没了解过

定义2

我们为 \(sa\) 数组衍生另外两个定义

\(hgt[i]\)：后缀 \(str[sa[i]...]\) 与 \(str[sa[i-1]...]\) 的最长公共前缀（height）

\(LCP(i,j)\)：后缀 \(str[sa[i]...]\) 和 \(str[sa[j]...]\) 的最长公共前缀

思路2

设 \(j=sa[ra[i]-1]\)

当依次计算 \(str[i...]\) 和 \(str[j...]\)（对应 \(i\) 在 \(sa\) 数组上的前一个后缀）

如果已经得知 \(h[i]=hgt[ra[i]]\)（表明 \(str[i]\) 和 \(str[j]\) 的最多前 \(h[i]\) 个字符相同）

而对比之下 \(str[i+1]\) 和 \(str[j+1]\) 则分别对应于前面砍掉了首字符，所以至少前 \(h[i]-1\) 个字符相同，\(h[i+1] \ge h[i]-1\)，对于该串只需从下标 \(h[i]-1\) 开始判断即可

因此求出 \(hgt\) 数组的复杂度是 \(O(n)\)

如果对于两个串 \(str[i...]\) 和 \(str[j...]\) 且满足 \(ra[i] < ra[j]\)

由于 \(i\) 和 \(j\) 排名不相邻（相邻就直接是 \(hgt\) 了，其结果肯定不会比 \(sa\) 当中对应 \(i\) 到 \(j\) 的 \(hgt\) 更优

由 \(hgt\) 的传递性可以得出结论

\[LCP(i,j) = min(hgt[ra[i]+1],hgt[ra[i]+2],...,hgt[ra[j]])\]

这一部分用 \(RMQ\) 预处理后即可 \(O(1)\) 求解任意 \(LCP(i,j)\)

举例2

ababaaab
h[i] str[i] str[j]
3 ababaaab abaaab
2 babaaab baaab(注意这和上一个 str[j+1]没有关系)
2 abaaab ab
1 baaab b
0 aaab
2 aab aaab
1 ab aab
0 b ababaaab

完成版

#include<bits/stdc++.h>
#define fast_io() do{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);}while(0)
#define print(a) printf("%a",(ll)(a))
#define printbk(a) printf("%lld ",(ll)(a))
#define println(a) printf("%lld\n",(ll)(a))
#define rep(i,j,k) for(int i = (j); i <= (k); ++i)
#define rrep(i,j,k) for(int i = (j); i >= (k); --i)
#define erep(i,u,v) for(int i = head[u], v = to[i]; ~i; v = to[i = nxt[i]])
#define mod(a,b) (((a)%b+b)%b)
#define int int_fast32_t
using namespace std;
using ll = long long;
const int MAXN = 1e5+11;
struct SA {
    string str;
    int n;
    vector<int> sa,ra,tmp,hgt;
    void build(const string &s,bool lcp = false) {
        str = s;
        n = s.length();
        sa = ra = tmp = vector<int>(n);
        for(int i = 0; i < n; i++) {
            sa[i] = i;
            ra[i] = str[i];
        }
        auto k = 0;
        auto cmp = [&](int i,int j) -> bool {
            if(ra[i] != ra[j]) return ra[i] < ra[j];
            int ri = i+k < n ? ra[i+k] : -1;
            int rj = j+k < n ? ra[j+k] : -1;
            return ri < rj;
        };
        for(k = 1; k <= n; k <<= 1) {
            sort(sa.begin(),sa.end(),cmp);
            tmp[sa[0]] = 0;
            for(int i = 1; i < n; i++) {
                tmp[sa[i]] = tmp[sa[i-1]]+cmp(sa[i-1],sa[i]); // 依靠 ra 的结果，不能覆盖 
            }
            auto flag = false;
            for(auto i = 0; i < n; i++) {
                ra[i] = tmp[i];
                if(ra[i] == n-1) flag = true; // opt
            } 
            if(flag) break;  // opt
        }
        if(!lcp) return;
        hgt = vector<int>(n);
        int h = 0;
        for(int i = 0; i < n; i++) {
            if(ra[i]-1 < 0) { // 有溢出风险 
                hgt[ra[i]] = h = 0;
                continue;
            }
            int j = sa[ra[i]-1];
            if(h) h--;
            for(int t=max(i,j); t+h < n; h++) {
                if(str[i+h]!=str[j+h]) break;
            }
            hgt[ra[i]] = h;
        }
    }
}sa;
int32_t main() {
    fast_io();
    string s;
    cin >> s;
    sa.build(s,1);
    for(int i = 0; i < sa.str.length(); i++) {
        cout << sa.hgt[sa.ra[i]] << " ";
        cout << sa.str.substr(i) << " " << (sa.ra[i]-1 < 0 ? " " : sa.str.substr(sa.sa[sa.ra[i]-1])) << endl;
}
return 0;

}

Q：如何验证你的算法正确性？

A: https://ift.tt/SFOJKkr

更多查询：https://ift.tt/zO4N1uf

via Caturra’s Blog

September 10, 2024 at 10:46AM