时间戳

首页 > 技术文章 > 【字符串】后缀数组

【字符串】后缀数组

purinliang 2021-01-17 18:49 原文

后缀排序

倍增算法

\(n\) 字符串的长度。
\(m\) 当前后缀（离散化后）的值域。对于char可以跳过离散化，初值取128即可，对于int要离散化，初值取n即可，初值要保证覆盖整个值域。
\(sa[i]\) 排名为 \(i\) 的后缀的起始位置。
\(rk[i]\) 起始位置为 \(i\) 的后缀的排名。

验证：https://www.luogu.com.cn/problem/P3809

const int MAXN = 1000000 + 10;
int n, m, ct[MAXN], tp[MAXN];
int sa[MAXN], rk[MAXN], ht[MAXN];

void RadixSort() {
    for(int i = 0; i <= m; ++i)
        ct[i] = 0;
    for(int i = 1; i <= n; ++i)
        ++ct[rk[i]];
    for(int i = 1; i <= m; ++i)
        ct[i] += ct[i - 1];
    for(int i = n; i >= 1; --i)
        sa[ct[rk[tp[i]]]--] = tp[i];
}

bool Compare(int i, int j, int l) {
    if(tp[sa[i]] == tp[sa[j]]) {
        if(sa[i] + l <= n && sa[j] + l <= n) {
            if(tp[sa[i] + l] == tp[sa[j] + l])
                return 1;
        }
    }
    return 0;
}

void SuffixSort(char *s) {
    n = strlen(s + 1), m = 128;
    for(int i = 1; i <= n; ++i) {
        rk[i] = s[i];
        tp[i] = i;
    }
    RadixSort();
    for(int l = 1;; l <<= 1) {
        m = 0;
        for(int i = n - l + 1; i <= n; ++i)
            tp[++m] = i;
        for(int i = 1; i <= n; ++i) {
            if(sa[i] > l)
                tp[++m] = sa[i] - l;
        }
        RadixSort();
        swap(tp, rk);
        m = 1;
        rk[sa[1]] = 1;
        for(int i = 2; i <= n; ++i) {
            if(Compare(i - 1, i, l) == 0)
                ++m;
            rk[sa[i]] = m;
        }
        if(m == n)
            break;
    }
}

最小循环表示

把字符串S循环移动，找字典序最小的那个表示。

把字符串 \(S\) 复制变成字符串 \(S+S\) ，然后变成后缀排序的问题。前[1,n]的后缀数组中的最小的那个就是答案。当然可能会有多个循环表示的串都是代表同一个东西的，这样要注意题目的特殊限制，也可以利用这个最小循环的串构造出来之后在 \(S+S\) 中查找第一个匹配位置。

验证：https://www.luogu.com.cn/problem/P4051

这一题只需要把最小表示串找出来，所以就找任意一个即可。注意n的取值要和后缀数组中字符串相匹配。

        int n = strlen(str + 1);
        for(int i = 1; i <= n; ++i)
            str[i + i] = str[i];
        str[n + n + 1] = '\0';
        SuffixSort(str);
        int pos = min_element(rk + 1, rk + 1 + n) - rk;
        for(int i = 1; i <= n; ++i)
            putchar(str[pos + i - 1]);
        putchar('\n');

假如字符集很大，那么后缀自动机就会失效，这个时候后缀数组可以通过离散化解决，然后字符串取离散化后的结果，m初始值就取n（而不是128）。

所有循环表示

找出S的所有循环表示，并把他们按字典序排列。

验证：https://www.luogu.com.cn/problem/P4051

对于后缀数组来说，这个问题和上面的一模一样，直接取前n个的rk重新排序就行。

        int n = strlen(str + 1);
        for(int i = 1; i <= n; ++i)
            str[i + n] = str[i];
        SuffixSort(str);
        for(int i = 1; i <= n; ++i)
            p[i] = {rk[i], i};
        sort(p + 1, p + 1 + n);
        for(int i = 1; i <= n; ++i)
            putchar(str[p[i].second + n - 1]);
        putchar('\n');

在文本串S中查找模式串T的所有出现位置

验证：https://www.luogu.com.cn/problem/P3375

对S构造后缀数组，然后在后缀数组sa上面二分，二分枚举到一个位置M，排名为M的后缀的起始位置是sa[M]，然后对sa[M]的后缀和模式串T暴力比较，得出的结果可能是M偏大、M偏小，或者刚刚好，找到第一个刚刚好的位置，然后同理找到最后一个刚刚好的位置，中间的就是所有的出现次数。因为寻找的是以T开头的所有后缀的起始位置，所以他们必定是在后缀数组中连续的一个区间。

int sl, tl;
char s[MAXN];
char t[MAXN];

int Check(int pos) {
    return strncmp(s + sa[pos], t + 1, tl);
}

int FirstEqual() {
    int L = 1, R = sl;
    while(L < R) {
        int M = (L + R) / 2;
        if(Check(M) >= 0)
            R = M;
        else
            L = M + 1;
    }
    return Check(L) == 0 ? L : sl + 1;
}

int LastEqual() {
    int L = 1, R = sl;
    while(L < R) {
        int M = (L + R + 1) / 2;
        if(Check(M) <= 0)
            L = M;
        else
            R = M - 1;
    }
    return Check(L) == 0 ? L : 0;
}

vi GetAllOccurences() {
    sl = strlen(s + 1);
    tl = strlen(t + 1);
    SuffixSort(s);
    int L = FirstEqual();
    int R = LastEqual();
    vi ans;
    for(int i = L; i <= R; ++i)
        ans.eb(sa[i]);
    srt(ans);
    return ans;
}

最长公共前缀

下面的约定中，lcp的参数是字符串，并且用i表示suf(i)，sa[i]表示第i名的后缀，即suf(sa[i])

lcp(i,j)=lcp(j,i)
lcp(i,i)=len(suf(sa[i]))=n-sa[i]+1

$lcp(sa[i],sa[j])=\min\limits_{k\in[i+1,j]}(lcp(sa[k],sa[k-1])) $
即两个相隔甚远的后缀的lcp可以用相邻后缀的lcp的rmq求出来。

设 ht[i]=lcp(sa[i],sa[i-1]) ht[1]=0 即第i名的后缀和它前1名的LCP的长度。

那么 \(lcp(sa[i],sa[j])=\min\limits_{k\in[i+1,j]}ht[k]\)

那么ht[rk[i]]>=ht[rk[i-1]]-1

求ht数组 代码

然后，求两个后缀的lcp就变成RMQ问题，可以用ST表加速。

比较子串的字典序

子串A[a,b] 和B[c,d]

若lcp(sa[a],sa[c])>=min(|A|,|B|) ，则A<B等价于|A|<|B|
否则，A<B等价于rk[a]<rk[c]

贪心取字符串的首尾组成字典序最小的新串：比较子串s和子串t的反串的字典序，对S+'#'+S构造后缀数组。

在字符串T中查找子串S

对T构造后缀数组，然后在T的后缀数组上二分，暴力匹配S。这是一个在线的算法，比起AC机的优势。单次匹配复杂度可能优于KMP。

本质不同子串的数目

验证：https://www.luogu.com.cn/problem/P2408

所有的子串一共有\(\frac{1}{2}n(n+1)\)个，其中对于每个后缀，重复的恰好是ht的数量。

\(\frac{1}{2}n(n+1)-\sum\limits_{i=2}^{n} ht[i]\)

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

出现至少k次，意味着至少连续k个后缀的LCP是这个串。

故是连续k-1个ht的最小值，枚举所有的最小值求最大值。

https://codeforces.com/contest/149/problem/E

题意：给定n=1e5长的字符串S，t=100次询问，每次询问m=1e3长的字符串T，问是否可以从S中选择两个不相交的非空子串s1,s2使得s1+s2=T。有一个哈希的做法，不过TLE22了，枚举s1的长度那么可以直接算出s2的长度，总共有1e3种长度，在S上跑1e3次尺取哈希，然后用数据结构找出第一个哈希值等于s1的位置和最后一个哈希值等于s2的位置比较，复杂度最差为O(nmt)。改用后缀数组的优势在于不再需要跑原字符串的长度，构造的复杂度为nlogn，然后类似“找字符串T的所有出现位置”的做法，找出那个连续区间然后套ST表查出来，复杂度是O(nlogn+tmlogn)。ST表中传入的数组a为后缀数组sa。

推荐阅读