后缀数组/基数排序 Suffix Array

一种可以做到$O(n)$复杂度的字符串数据结构。

用途

求得每个后缀的字典序排名,并对其进行扩展的应用。

求法

二分法

使用hash+sort,两个串比对时,二分两个串最早不相同的字符并进行比对。

优化的是cmp的过程。

复杂度$O(n\log^2 n)$。

倍增法

具体请查看百度第一篇博客,里面讲的比较清楚,大概就是每次都把串压成一个数,压在一起再进行比对,一是压的过程是可以倍增的,二是比对的过程是可以优化的(使用双关键字基数排序进行优化)。

复杂度$O(n\log n)$。

这里讲一下双关键字基数排序。

双关键字基数排序

假设有一对pair。

一个数组装了很多个pair。

我们怎么在$O(n)$的时间内对pair排序?

你可能会说桶排。那么双关键字怎么处理?桶套桶?

总而言之这里有一个时空复杂度都是$O(k(n+m))$的优秀算法辣($k$为关键字个数,$n$为桶大小,$m$为元素个数)

大体思路如下:

我们先对第二关键字排序(优先级较小),通过对桶搞事我们可以得到每个pair 在第二关键字下 排名可能的范围

用同样的方法对桶搞事我们可以得到每个pair 在第一关键字下 排名可能的范围。

然后问题来了。如果第一关键字不同的话我们其实只要对第一关键字排名就行了,但如果第一关键字相同,每个pair在第一关键字下排名可能的范围可能较大而不能精确。

这要求我们使用第二关键字排名可能的范围。

我们使用这个范围对pair随便分配一个合法的具体排名(因为没有第三关键字的约束)。然后我们以排名从后到前的方式再遍历一遍pair,给pair在第一关键字下分配一个精确的排名(范围内最大)。

为什么这样可行?因为第二关键字从后到前遍历,先被遍历到的会被分配一个在第一关键字下范围内较大的排名,而较小的会让给前面的。这样保证了第一关键字相同的情况下,第二关键字从小到大排序。

很神奇吧?

其实基数排序应该也是一样的道理。 我们可以把一个数按位拆成$\log n$左右个关键字,前置补零。那么对数排序实际上就变成了一个关键字排序。桶的大小足够小,这样子我们就可以得到一个优秀的排序算法。

具体代码实现请参考:

// Code by ajcxsu
// Problem: pair

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;
int x1[N], x2[N], c[N], rk1[N], d[N], rk2[N];
// c:桶  rk1:第二关键字排序结果 d:桶 rk2:第一关键字排序结果

int main() {
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>x1[i]>>x2[i]; // input pairs
    /* base sort */
    for(int i=0;i<n;i++) c[x2[i]]++;
    for(int i=1;i<N;i++) c[i]+=c[i-1];
    for(int i=0;i<n;i++) rk1[c[x2[i]]--]=i;
    // for(int i=1;i<=n;i++) cout<<rk1[i]<<' ';
    // cout<<endl;
    for(int i=0;i<n;i++) d[x1[i]]++;
    for(int i=1;i<N;i++) d[i]+=d[i-1];
    for(int i=n;i>=1;i--) rk2[d[x1[rk1[i]]]--]=rk1[i];
    /* output */
    for(int i=1;i<=n;i++) cout<<x1[rk2[i]]<<' '<<x2[rk2[i]]<<endl; // output pairs
    return 0;
}

Code

// Code by ajcxsu
// Problem: sa_true

#include<bits/stdc++.h>
using namespace std;

const int N=1e6+10;
int x[N], y[N], sa[N], c[N]; // 第一关键字(rank) 第二关键字排序结果 后缀(第一关键字)排序结果 桶
char s[N];
int n, m; // length

void getsa() {
    for(int i=1;i<=n;i++) c[x[i]=s[i]]++; // 初始化第一关键字
    for(int i=1;i<=m;i++) c[i]+=c[i-1];
    for(int i=1;i<=n;i++) sa[c[x[i]]--]=i; // 初始化第一次sa
    int num;
    for(int k=1;k<=n;k<<=1) {
        num=0;
        /* 求第二关键字rank(非常规方法) */
        for(int i=n-k+1;i<=n;i++) y[++num]=i; // [n-k+1, n]没有第二关键字,因此对第二关键词排名第一
        for(int i=1;i<=n;i++) if(sa[i]>k) y[++num]=sa[i]-k;
        // 直接从小到大作为第二关键字枚举sa得到从小到大的第二关键字位置
        // 如果位置合法,插入第一关键字
        /* 求第一关键字rank(新sa) */
        fill(c+1, c+1+m, 0);
        for(int i=1;i<=n;i++) c[x[i]]++;
        for(int i=2;i<=m;i++) c[i]+=c[i-1];
        for(int i=n;i>=1;i--) sa[c[x[y[i]]]--]=y[i], y[i]=0;
        swap(x, y); // 把x数组拷到y中去
        x[sa[1]]=1; // 更新第一关键字
        num=1;
        for(int i=2;i<=n;i++)
            x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]?num:++num);
        if(num==n) break;
        m=num; // 更新字符集大小
    }
    for(int i=1;i<=n;i++) cout<<sa[i]<<' ';
    cout<<endl;
}

int rank[N]; // 排名
int height[N]; // height
void gheight() {
    for(int i=1;i<=n;i++) rank[sa[i]]=i;
    int k=0;
    for(int i=1;i<=n;i++) {
        if(rank[i]==1) continue;
        if(k) k--;
        int j=sa[rank[i]-1];
        while(j+k<=n && i+k<=n && s[j+k]==s[i+k]) k++;
        height[rank[i]]=k;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin>>(s+1);
    n=strlen(s+1), m='z';
    getsa();
    return 0;
}

DC3法

不会。

复杂度$O(n)$,据说常数大。

LCP 最长公共前缀

SA的主要扩展。

定义

$suf(i)$:代表后缀i-n的字符串。

$LCP(i, j)=LCP(suf(sa_i), suf(sa_j))$:排名为i的后缀和排名为j的后缀的LCP。

$height_i=LCP(i, i-1)$:排名为i的后缀和排名为i-1的后缀的LCP。

一些定理证明

定理一

$$LCP(i, k)=min(LCP(i, j), LCP(j, k))\ (i< j< k)$$

证明: 假设$LCP(i,j)=la, LCP(j, k)=lb, A=suf(sa_i), B=suf(sa_j), C=suf(sa_k), lc=min(la, lb)$。

则$A_{la+1}\neq B_{la+1}, B_{lb+1}\neq C_{lb+1}$。

假设$C_{lc+1}=A_{lc+1}$。

则$A,C$的排名应相邻,而$A,C$中一定存在一个$X$使得$X_{lc+1}\neq B_{lc+1}$,B的排名却在AC中间,矛盾。

因此$C_{lc+1}\neq A_{lc+1}$。

显然$LCP(i, k)\geq lc$,因此$LCP(i, k)=lc$,证毕。

定理二

$$LCP(i,k)=min(LCP(j, j-1))\ (i\geq j> k)$$

由定理一显然。

我们要做的事情

如果求出了$height$,求任意两个后缀的LCP由定理二就变成了一个RMQ问题。

为了求出$height$我们需要临时再增加两个定义:

$rank_i$:排名为i的后缀的下标。

$h_i=height_{rank_i}$,下标为i的后缀和下标为i的后缀排名-1的后缀的LCP。

定理三

$$h_i\geq h_{i-1}-1$$

在完全理解$h_i$的含义下,直接去网上搜就能看懂。

我看的一篇:https://www.cnblogs.com/jinkun113/p/4743694.html

证明来自刘汝佳。

代码

上面有。

应用

咕咕咕

本文链接:https://acxblog.site/archives/suffix-array.html
本文采用 CC BY-NC-SA 3.0 协议进行许可