一种可以做到 $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

证明来自刘汝佳。

代码

上面有。

应用

咕咕咕