[后缀数组]总结

Template

算法逻辑：

对长度为1时进行排序
倍增长度k
{
    按第二关键字将第一关键字排序
    求出2*k长度下的SA
    求出2*k长度下的rank(即x数组)
}

模板：

#include <bits/stdc++.h>

using namespace std;
#define X first
#define Y second
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
typedef double db;
typedef long long ll;
typedef pair<int,int> P;
const int MAXN=1e6+10;
char s[MAXN];
int len,lmt,cnt[MAXN],sa[MAXN],x[MAXN],y[MAXN],cur;

void solve()
{
    for(int i=1;i<=len;i++)
        cnt[x[i]=s[i]]++;
    for(int i=1;i<=lmt;i++)
        cnt[i]+=cnt[i-1];
    for(int i=len;i>=1;i--)
        sa[cnt[x[i]]--]=i;
    
    for(int k=1;k<=len;k<<=1,lmt=cur)
    {
        cur=0;
        for(int i=len-k+1;i<=len;i++)
            y[++cur]=i;
        for(int i=1;i<=len;i++)
            if(sa[i]>k) y[++cur]=sa[i]-k;
        
        for(int i=1;i<=lmt;i++) cnt[i]=0;
        for(int i=1;i<=len;i++) cnt[x[i]]++;
        for(int i=1;i<=lmt;i++) cnt[i]+=cnt[i-1];
        //一定要按第二关键字从大往小枚举！ 
        for(int i=len;i>=1;i--)
            sa[cnt[x[y[i]]]--]=y[i];
        
        swap(x,y);cur=1;x[sa[1]]=1;
        for(int i=2;i<=len;i++)
            x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?cur:++cur;
        if(cur==len) break;
    }
}

int main()
{
    scanf("%s",s+1);
    len=strlen(s+1);lmt=130;
    solve();
    for(int i=1;i<=len;i++)
        printf("%d ",sa[i]);
    return 0;
}

注意：

1、可以利用基数排序直接算出排名

求出前缀和后其实就表示了该权值下的排名上界，每次将上界减一

因此要按第二关键字从大到小算SA

2、当已经出现$len$个$rank$时即可退出

Exercises

1、[BZOJ 4892]Dna

一共只有$n-m+1$个可能的串，加速比对过程即可

由于最大失配次数只有3次，因此可以利用$lcp$加速比对连续相同的部分！

复杂度降为$O(n*3*log(n))$

2、[Gym 101194F]

先用处理多字符串的套路连起来

找到第一个字符串的每个后缀在$rank$中最接近的不同字符串的后缀

那么对于后缀$i$的最短长度即为$max(lcp(rk[i],l[rk[i]]),lcp(rk[i],r[rk[i]]))+1$

为保证字典序最小用$lcp$来$O(logn)$进行比较

3、[BZOJ 3277]

先连起来，对每个后缀$x$二分可行长度$len$

判断长度是否可行，就是判断$lcp(x,y)\ge len$的$y$是否存在于$k$个字符串

由于$lcp$的单调性，可以左右分别二分出$y$的可行区间$[L,R]$

通过预处理出$least[R]$表示包含$k$个字符串的最右点，判断是否$L\le least[R]$即可

Tip1：可以发现同一字符串中$len[i]\ge len[i-1]-1$，这样像推$height$一样推$len$就能做到单$log$

Tip2：时刻注意自己枚举的是排名还是原串位置

4、[Gym 101955B]

关键点在于误差小于$1e-9$！

由于概率大于0.5的只能有一个字母，将原始字母设为概率最大后失配必然使得相乘概率小于0.5

也就是说，最多失配30个字母就可以不用统计了！这样就和前面的[BZOJ 4892]相同了

Tip：为保证精度可以用指数运算，这样就能使用前缀和了

5、[Gym 102028H]

知道本质不同的字符串的算法即可

问题转化为左端点固定，右端点为一个区间的最大值的和

可以发现对于此问题明显只有单调栈中的元素有分段的贡献

从而可以从后往前维护一个单调减的单调栈，每次退栈时用线段树区间修改即可

6、[BZOJ 3238]

求$\sum lcp(i,j)$可以转化为每个$height$的贡献

由于$lcp$的单调性，对于每个$i$用单调栈找到其提供贡献的区间$[L,R]$

最终答案即为$\sum (i-L+1)*(R-i+1)*h[i]$

Tip1：单调栈判断时保证一个小于等于一个小于，防止相等时重复计数

Tip2：注意$h[i]$是与前一位的$lcp$，计数时按两两间理解，自己乘自己是允许的

7、[BZOJ 4310]

在本质不同的字符串序列中二分排名，每次先算出该字符串的位置

判断就是从后往前每次加一个字符，只要字典序比二分串大就分割一段，判断段数是否满足

Tip：注意对两相同位置求$lcp$时特殊处理！

8、[BZOJ 3879]

将查询串按$rank$排序，算出两两间的$lcp$作为$height$

接下来就和[BZOJ 3238]完全相同了

9、[BZOJ 4278]

用$rank$的比较快速判断两后缀字典序的大小，贪心选择字典序小的即可

10、[BZOJ 2320]

11、[BZOJ 2119]

[后缀数组]总结

原文：https://www.cnblogs.com/newera/p/10189753.html