后缀数组基础

终于来了……

一车的定义来了

• 记字符串为$s[1,n]$，则我们称从𝑖开始的后缀为$s[i,n]$。

• 我们称所有后缀为集合$s[1,n],s[2,n],…,s[n,n]$。

• 对该集合排序时按照字典序排序，这样可以得到一个“后缀”数组。

• $Rank[i]$表示从𝑖开始的后缀在排序后的的数组中的排名（升序）

• $sa[i]$表示排名为i的后缀的首字符的位置（即从开始的后缀

  容易发现$Rank[sa[i]]=i$

• $height[i]$表示排名为i的后缀和排名为i-1的后缀LCP（最长公共前缀）的长度

倍增算法

（倍增算法用的最广泛并且最短，有线性做法但是很难用（不如直接SAM

具体而言，我们分轮数进行后缀数组的构建：

在第i轮的时候，我们把每一个后缀的前$2^{i+1}$位进行排序（不够就直接排序就可以，按照以字典序为0的字符插进去一样的改

在倍增的过程中我们需要用到基数排序：

我们如果要求这一路的话我们应该是已经把上一轮求过了，就是说前面一半字符的排名都已经求过了

那么我们可以把前面板部分缩成一个数字

那么：后半部分……其实是可以进行转化的：

如果说一个字符串有当前的后半部分的话，那么这个后半部分应该是拎一个后缀的前缀，就是当前$i+2^k$位置后缀的前缀

那么我们也可以把后半部分转化成一个数字来进行排序

那么说明当前我们把所有的后缀转化成了一个双关键字排序

那么我们就先按照后半部分进行一次排序（因为第一关键字已经排过序了

那么因为基数排序是稳定的所以我们并不需要担心第一关键字的顺序变混乱

上面是求得sa数组的算法

height数组是有一个性质的：$height[Rank[i]]>=height[Rank[i-1]]+1$（我不想证明了背过结论就可以了

然后就可以线性的求height数组了

我觉得下面代码的注释还挺详细的

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e6 + 10;
int n, sa[maxn], x[maxn], y[maxn], rk[maxn], height[maxn], m, c[maxn];
/*
sa:排名为i的是哪一个后缀
x：第一关键字
y：第二关键字
rk：第i个后缀的排名
height：排名第i的后缀和排名第i-1的后缀的LCP
c：基数排序的时候所要用到的桶
*/
char s[maxn];
void get_sa()
{
    /* 这个地方要用到基数排序来进行求组 */
    for (int i = 1; i <= n; i++)
        ++c[x[i] = s[i]];
    for (int i = 2; i <= m; i++)
        c[i] += c[i - 1];
    for (int i = n; i; i--)
        sa[c[x[i]]--] = i;
    for (int k = 1; k <= n; k <<= 1)
    {
        int num = 0;
        for (int i = n - k + 1; i <= n; i++)
            y[++num] = i;
        for (int i = 1; i <= n; i++)
            if (sa[i] > k)
                y[++num] = sa[i] - k;
        for (int i = 1; i <= m; i++)
            c[i] = 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; i--)
            sa[c[x[y[i]]]--] = y[i], y[i] = 0;
        swap(x, y);
        num = 1;
        x[sa[1]] = 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 = n;
    }
}
/*void get_height()
{
}*/
signed main()
{
    ios::sync_with_stdio(false);
    cin >> s + 1;
    n = strlen(s + 1);
    m = 122;
    get_sa();
    // get_height();
    for (int i = 1; i <= n; i++)
        cout << sa[i] << ' ';
    cout << endl;
    return 0;
}

例题

P4051 [JSOI2007]字符加密

题目链接

板子题……

我们对于一个环来说最好的解决方法是什么呢？

向后拓展一倍嘛

向后拓展一倍之后，再接着进行一次后缀数组的求解，如果我们求出来了后缀数组的排名，其实也就相当于是求出来了原来循环重构的排名

因为字典序他是从前向后考虑的，如果前面就已经不一样了，那么后面就可以不用考虑了，就算是考虑到了也没有什么关系的，因为那证明了前面n位是一样的，那么其实随便输出任何一个就可以了（或者说他们的顺序就没什么考虑性了

P4248 [AHOI2013]差异

题目链接

这个题为什么我加了快读之后变慢了我不理解

（我所做过的单调栈的第一道题

首先题目中的那个公式

前边一部分是可以提出来的

所以直接搞后半部分就可以了

后半部分就是一个单调栈的板子题了

求出来height数组

看一下每一个height数组都可以拓展到那一位就可以了

不过似乎ST表加上二分也是可以的

但是显然O(N)更优吧

所以还是单调栈比较好

不过这个题我是抄的题解

这篇题解整得特别妙啊

在搞单调栈的时候首先先来了一下找最左端比他自己小的

如果实在这个最左端的左边的话就可以进行继承了

因为j+1-i之间的h[i]一定是不能够进行更新的，一定是在j左边的点为答案

然后就可以搞了

P2178 [NOI2015] 品酒大会

题目链接

听说Rainbow是李煜东，Freda是他的npy

这个题我们把所有的lcp对应的几个后缀求出来，然后后缀和一下

首先如果说连续的几个lcp相同的是可以合并的

那么合并我们就可以用到并查集

并查集记录一下size和fa就可以

我么从大到小枚举

以为大的也可以给小的做出贡献

那么我们就可以把他们放到并查集里

每次并查集更新都算一次答案的改变值（就省得费时费力一个一个算了，继承一下

其他的看注释

P1117 [NOI2016] 优秀的拆分

题目链接

这个题记录一下每一个端点开始的AA串和结尾的AA串然后乘起来就可以了

那么，我们考虑计算

我们枚举出来一个长度

那么我们在找到这个长度的时候，进行一下拆分

我们将原来的串上面每隔len个点都标记一个关键点出来，那么，我们在统计一下这个关键点和下一个关键点的lcp和lcs

首先这两嗯东西所代表的应该是一样的字串

那么这两个字串连起来就是可以相等的

那么如果lcp+lcs是大于len的那么说明是有答案的

那么在统计一下

lcp和lcs是可以用sa进行计算的

（结束

P4143 采集矿石

有生之年第一道黑题

看注释吧……

完结撒花