后缀数组

后缀数组，即 (text{SA(Suffix Array)})，主要关系到两个数组：

(sa)

对于 (sa_i) 表示将所有后缀排序后第 (i) 小的后缀的编号，也就是排名为 (i) 的后缀的位置

此处的排序是按照字典序排的
(rk)

(rk_i) 表示从第 (i) 个位置开始的后缀的排名

两个数组满足以下性质 (sa_{rk_{i}}=rk_{sa_{i}}=i)

借用 (text{OI-wiki}) 的一张图用于解释后缀数组内的 (sa) 和 (rk) 数组

求后缀数组

(text O(n^2log n))

最为暴力的想法

直接大力 sort 排序，不难发现排序需要进行 (text O(nlog n)) 次字符串比较，每次比较复杂度均为 (text O(n))，所以是 (text O(n^2log n))的

这个很明显非常不优，肯定是不推荐的
(text O(n log^2n))

倍增做法

首先对字符串 (s) 的所有长度为 (1) 的子串进行排序，得到排序后的编号数组 (sa_1) 和排名数组 (rk_1)。

用两个连起来的长度为 (1) 的子串作为排序的两个关键字(靠前的子串为第一关键字)进行排序，这样就可以获得长度为 (2) 的子串排序的结果

然后我们再用两个长度为 (2) 的子串作为排序的两个关键字排序，以此类推，假设倍增后长度为 (w) 则当 (i+w) 加起来比 (n) 大的时候视 (s_{i+w}) 为无限小

在最后我们倍增出来的长度已经大于等于 (n) 的时候就可以得到我们需要的后缀数组 (sa)

显然倍增的过程是 (text O(log n)) ，而每次倍增用 sort 对子串进行排序是 (text O(nlog n)) ，而每次子串的比较花费 (2) 次字符比较

这个看起来就优多了，复杂度是 (text{O}(n log^2 n)) 的
点击查看代码
```
namespace SA{
    int sa[N],rk[N],oldrk[N];
    inline bool cmp(int x,int y,int w){
        return (rk[x]!=rk[y])?(rk[x+w]
```
解释一下代码

首先 cmp 是双关键字的，这是因为字典序排的没啥好说的

为什么我们要复制一遍 rk 呢？(oldrk)

这很明显是因为在计算同时也在修改 rk，原本的 rk 会被覆盖

最后的判断是因为如果两个子串的字典序相同我们则需要去重
(text{ O}(n log n))

虽然上面那份代码已经可以通过 LOJ 的后缀排序，但我们还是认为 (text O(n log^2 n)) 不够优怎么办？发现主要瓶颈在于 (text O(n log n)) 的 sort 排序

那么为什么不用线性的排序方法呢？计数排序，基数排序

我们发现后缀数组的排序是双关键字，而且值域是排名也就是严格 (text O(n)) 的

所以可以使用基数排序来优化我们上面的倍增做法，这样我们就可以得到一份常数巨大的 (text O(n log n)) 做法

常数巨大到连 (text O(n log^2 n)) 都跑不过，甚至很可能会T掉，因此我们需要常数优化
- 第二关键字无需基数排序
  
  第二关键字排序的实质其实就是把超出字符串范围的 (sa_i) 放到 (sa) 数组头部，剩下的依原顺序放入
  
  因此我们完全可以直接完成而不是基数排序
- 优化计数排序的值域
  
  我们在计算完 (rk) 只会就会留下一个服务器托管(tot)，这个 (tot) 就是当前排序的值域，可以来跑基数排序而不再用 (n)
这两个(尤其是第二个)优化非常显著，这样就可以跑过 (text O(n log^2 n)) 了，跑不过就是写假了，因为这样写常数会很小
点击查看代码
```
namespace SA{
    int sa[N],rk[N],oldrk[N],oldsa[N],w,cnt[N],key[N];
    inline bool cmp(int x,int y,int w){
        return (oldrk[x]==oldrk[y])&&(oldrk[x+w]==oldrk[y+w]);
    }
    inline void Init(char *s){
        int n=strlen(s+1),m=127,tot;
        for_(i,1,n) 
            rk[i]=s[i],
            ++cnt[rk[i]];
        for_(i,1,m) 
            cnt[i]+=cnt[i-1];
        _for(i,n,1) sa[cnt[rk[i]]--]=i;
        for(int w=1;;ww) 
                    oldsa[++tot]=sa[i]-w;
            memset(cnt,0,sizeof(cnt));
            for_(i,1,n) 
                ++cnt[key[i]=rk[oldsa[i]]];
            for_(i,1,m) 
                cnt[i]+=cnt[i-1];
            _for(i,n,1) 
                sa[cnt[key[i]]--]=oldsa[i];
            memcpy(oldrk+1,rk+1,n*sizeof(int));
            tot=0;
            for_(i,1,n)
                rk[sa[i]]=((cmp(sa[i],sa[i-1],w))?(tot):(++tot));
            if(tot==n)
                break;
        }
    }
}
using namespace SA;
```
这里有一些可以卡常的点
- 将 (rk_{oldsa_i}) 存下来，减少不连续内存访问
- 用函数来计算是否重复减少不连续内存访问
(text O(n))

一般是用不到的，(text O(n))做法虽然跑的比倍增要快但是空间和码量都巨大

有两种做法，SA-IS 和 DC3，我都不会

(text{height}) 数组

定义

首先我们要进行一些定义

后缀(i)

我们为了方便把从 (i) 开始的后缀称为后缀 (i)
(text{LCP})(最长公共前缀)

服务器托管

(text{LCP}(x,y))是指字符串 (x) 与字符串 (y) 的最长公共前缀(的长度)，在这里指后缀 (x) 与后缀 (y) 的最长公共前缀(的长度)
(text{height}) 数组的定义

(height_i=text {LCP}(sa_i,sa_{i-1})) ，即第 (i) 名的后缀与它前一名((i-1))的后缀的最长公共前缀

注意这里是排名

(height_1=0)

实现

实现 (text O(n)) 求 (text{height}) 数组需要一个引理

(height_{rk_{i}}ge height_{rk_{i-1}-1})

这个引理非常好啊，让人脑洞大开(物理)

下面是证明

当我们知道这个引理之后我们就可以暴力通过引理求 (text{height}) 数组了

inline void Init_H(){
    int tot=0;
    for_(i,1,n){
        if(rk[i]==0) continue;
        if(tot) --tot;
        while(s[i+tot]==s[sa[rk[i]-1]+tot]) ++tot;
        height[rk[i]]=tot;
    }
}

(k) 不会超过 (n) ，因此最多减 (n) 次，所以最多也就只会加 (2n) 次

复杂度是严格 (text{O}(n)) 的

应用&题目

后缀数组的应用非常多啊，我们一一列举

P3806 后缀排序

这个是模板题，没啥好说的直接求即可
BZOJ5673 求可重叠最长重复子串

最暴力的思路就是直接暴力比较子串和子串，复杂度 (O(n^2))

但是我们直接就发现实际上求得是 (text{height}) 数组最大值

因为BZOJ交不了所以我没写，口胡的思路
P4051「JSOI2007」字符加密

都说是 (text{SA}) 板子题，但是我一眼没看出来，菜

哦我读假题了，这里其实是长度为 (n) 的一堆子串而不是全排序

仔细看一看就可以发现其是一个环，然后把环直接大力展开，这样我们就得到了一个二倍长度的字符串

然后我们就可以跑后缀数组了，求出 (sa) 之后直接大力判其后缀有没有第 (n) 个后缀即可，复杂度 (text O(n log n)) 完全可过
- 核心代码
```
inline void In(){
    scanf("%s",s+1);
    int len=strlen(s+1);
    for_(i,1,len) s[i+len]=s[i];
    Init(s);
    int newlen=strlen(s+1);
    for_(i,1,newlen){
        if(sa[i]+len>2*len) continue;
        putchar(s[sa[i]+len-1]);
    }
}
```
P2463 Sandy 的卡片

做的第一道不是板子的后缀数组题纪念

先前后作差求出其差值也就是新的字符串，然后把所有串连接在一起，用后缀数组求出(text{LCP})，然后二分长度，每次从头到尾扫一遍

代码比较冗长
- 核心代码
```
inline void In(){
    n=read();
    for_(i,1,n){
        l[i]=read();
        for(int j=1;j1)mx=max(mx,a[i][j]-a[i][j-1]);
        }
        rt=min(rt,l[i]);
    }
    for(int i=1;i>1))
            ans=mid+1,lt=mid+1;
        else rt=mid-1;
    }
    print(ans,"n");
}
```
P4248 「AHOI2013」差异

这个题目看起来就非常板啊，首先我们发现前面两项其实是定值，为 (frac{n(n-1)(n+1)}{2})，没啥好说的

然后后面的 (text{LCP}) 如何维护呢？

在我对 (text{height}) 数组引理证明时用了两个定理

这两个定理随便挑一个再肆意转化一下就能发现 (text{LCP}(i,j)) 其实就是 (min{height[rk_i+1]sim height[rk_j]})，然后这样就是一个非常经典的单调栈问题了
- 核心代码
```
inline void In(){
    scanf("%s",s+1);
    Init(s);
    Init_H(s);
    int n=strlen(s+1),ans=0;
    for_(i,1,n){
        while(height[STA[top]]>height[i]) --top;
        l[i]=i-STA[top];
        STA[++top]=i;
    }
    STA[++top]=n+1;
    height[n+1]=-1;
    _for(i,n,1){
        while(height[STA[top]]>=height[i])--top;
        ans-=2*height[i]*l[i]*(STA[top]-i);
        STA[++top]=i;
    }
    print(ans+n*(n-1)*(n+1)/2,"n");
}
```
P2336 「SCOI2012」猫星球上的点名

一眼看过去似乎没什么思路，但是发现用AC自动机可以随便搞啊！但是这是后缀数组题单所以我要用后缀数组(悲

发现(n)和(m)的范围很小，所以可以用一个非常暴力的思路来解决这个题

先把所有串连起来跑一个后缀数组，然后对每一个询问向前、向后扫描并把答案放入set，set判重并输出size

异常暴力的思路，还真能过

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net

相关推荐: GPT3.5 改用 GPT4 价格翻了30倍如何破局？ GPT 对话成本推演

场景介绍假设你搭建了一个平台，提供 ChatGPT 3.5 的聊天服务。目前已经有一批用户的使用数据，想要测算一下如果更换 GPT 4.0 服务需要多少成本？方案阐述如果是全切，最简单粗暴的方案就是根据提供 ChatGPT 3.5 消费的金额乘以一个倍数…

【学习笔记】字符串基础：后缀数组

后缀数组

求后缀数组

(text{height}) 数组

定义

实现

应用&题目

服务器托管，北京服务器托管，服务器租用，机房机柜带宽租用