后缀数组

前言

本高一蒟蒻实在不会后缀数组，又溜回来学啦~（话说这是第几次了？）

感觉理解能力日益下降，一个小时才看懂板子（大雾）

后缀数组是个神奇的玩意，具体怎么用我也不知道。

本渣不会DC3，所以只讲倍增。

基本定义

子串：在字符串s中任取$i<=j$，从第i个字符到第j个字符形成的字符串即为s的子串，记上面这玩意为$s[i,j]$。

后缀：从字符串某个位置i到字符串末尾形成的子串，即$s[i,len](1<=i<=len)$，记以i为开头的后缀为$suf(i)$。

后缀数组（sa）：表示排名为i的后缀的起始位置。

排名数组（rk）：表示起始位置为i的后缀的排名。

开始搞事qwq~

理解了上面这些定义之后，我们就可以乱搞了。直接快排$O(n^2logn)$多舒服。

先丢个图~（然后本蒟蒻就自己写了个$O(nlog^2n)$的垃圾算法）

实际上上面这张图完成第三次排序时就可以停止了。

一开始，我们可以根据每一位字符的ascii码得到当前情况下该位字符的排名$x_i$。（排名当然可以重复啦~）

然后第k次排序，对于第i位，我们将$x_i$作为第一关键字，$x_{i+2^{k-1}}$作为第二关键字。（显然的，当$i+2^{k-1}>n$时，第i位的第二关键字为0）

我们来考虑一下这为什么是可行的：

初始情况下，每一位所表示的字符串为以当前位为开头长度为1的字符串。

第k(k>1)次排序中，每一位所表示的字符串为以当前位为开头长度为$2^k$的字符串。比较两个关键字，相当于先比较前$2^{k-1}$个字符，再比较后$2^{k-1}$个字符。然后更新x数组。

因此，经过$logn$次的排序后，每一位所表示的字符串即以当前位为开头的后缀。x数组即为该字符串对应的rk数组。

对于每次排序，使用快速排序可以获得$O(nlog^2n)$的优秀算法（大雾）

然而有些聪(sang)明(xin)睿(bing)智(kuang)的出题人是会卡的，我们来想一下如何得到更优的时间复杂度。

我们观察发现（显然的），只有两个关键字，且关键字大小是$O(n)$的，因此我们对关键字进行基数排序即可，时间复杂度$O(nlogn)$。（基础知识，自行百度）

代码

我们定义$x_i$为第i位的关键字，$y_i$为第二关键字排名第i的位置，m为当前关键字种类数（初始值设为128即可），c为桶。

一开始先对每一位求出x值（第1次排序），对c做前缀和可以知道第一关键字为i时，排名最大可以是多少：

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;

第k次排序时，第$n-2^{k-1}+1$位到第n位的第二关键字为0，显然第二关键字排名最前：

for(int i=n-k+1;i<=n;i++)
    y[++num]=i;

若$sa[i]>2^{k-1}$，表明第$sa[i]$位可作为第$sa[i]-2^{k-1}$位的第二关键字：

for(int i=1;i<=n;i++)
    if(sa[i]>k)
        y[++num]=sa[i]-k;

清空桶，将$x_i$加入桶中，求前缀和：

for(int i=1;i<=m;i++)
    c[i]=0;
for(int i=1;i<=n;i++)
    c[x[i]]++;
for(int i=1;i<=m;i++)
    c[i]+=c[i-1];

第二关键字越大，在第一关键字相同的桶中排名越大：

for(int i=n;i;i--)
    sa[c[x[y[i]]]--]=y[i];

以上便完成一次基数排序。该次排序的sa数组已完成，可以直接循环求出新的x数组。

这里用y数组保存x数组，因为要用来计算新的x数组：

swap(x,y);x[sa[num=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;

后缀数组end.（后缀数组代码20行以内是真的哦~只要你缩行）

完整代码如下：

int n,c[100010]={0},x[200010],y[200010],sa[200010],rk[200010];
char s[100010];
inline void suffix_array(int m){
    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=1;i<=m;i++)
            c[i]+=c[i-1];
        for(int i=n;i;i--)
            sa[c[x[y[i]]]--]=y[i];
        swap(x,y);x[sa[num=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((m=num)==n)
            break;
    }
    for(int i=1;i<=n;i++)
        rk[sa[i]]=i;
    return;
}

height数组

待更…（可能会咕~）