后缀数组-学习

## 后缀数组(suffix array)
求的是每个后缀的排名，我们可以使用倍增法跟DC3,前者时间复杂度O(nlogn),后者O(n)
本文只考虑倍增法
然后我们定义了一些数组
sa[i]: 排名为i的后缀的位置
tp[i]: 第二关键字，性质同sa[i]
rak[i]: 第i个后缀的排名
tax[i]: 排序是需要用到的桶(基数排序)

排序部分

void Qsort()
{
    for(int i = 0; i <= m; i ++)
        tax[i] = 0;
    for(int i = 1; i <= n; i ++)
        tax[rak[i]] ++;
    for(int i = 1; i <= m; i ++)
        tax[i] += tax[i - 1];//知道当前排名前的相应后缀的数量
    for(int i = n; i >= 1; i --)
        sa[tax[rak[tp[i]]] --] = tp[i];//从后往前遍历
}

首先我们清空这个桶，然后开始计数
做前缀和的目的是为了知道当前排名之前的后缀的数量

获取第二关键字

        for(int i = 1; i <= w; i ++)//对于没有第二关键字的，放在最前面
            tp[++ p] = n - w + i;
        for(int i = 1; i <= n; i ++)
            if(sa[i] > w)
                tp[++ p] = sa[i] - w;//sa[i]往后w,往前w,凑2w,作为第二关键字
 

然后我们用第二关键字和上一轮的rak去更新sa,然后在用sa去更新本轮rak
洛谷p3809

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e6 + 5;
int n, m;
int sa[N], tp[N], rak[N], tax[N];
/*
sa[i]: 排名为i的后缀的首字母的位置
tp[i]: 第二关键字，性质同sa[i]
rak[i]: 第i个后缀的排名
tax[i]: 排序时用到的桶
sa[rak[i]] = i
rak[sa[i]] = i
*/
char s[N];
void Qsort()
{
    for(int i = 0; i <= m; i ++)
        tax[i] = 0;
    for(int i = 1; i <= n; i ++)
        tax[rak[i]] ++;
    for(int i = 1; i <= m; i ++)
        tax[i] += tax[i - 1];//知道当前排名前的相应后缀的数量
    for(int i = n; i >= 1; i --)
        sa[tax[rak[tp[i]]] --] = tp[i];//从后往前遍历
}
void get_SA()
{
    for(int i = 1; i <= n; i ++)
    {
        rak[i] = (int)s[i];
        tp[i] = i;
    }
    Qsort();
    for(int w = 1, p = 0; p < n; m = p, w <<= 1)//倍增法
    {
        p = 0;
        for(int i = 1; i <= w; i ++)//对于没有第二关键字的，放在最前面
            tp[++ p] = n - w + i;
        for(int i = 1; i <= n; i ++)
            if(sa[i] > w)
                tp[++ p] = sa[i] - w;//sa[i]往后w,往前w,凑2w,作为第二关键字
        Qsort();
        swap(tp, rak);
        rak[sa[1]] = p = 1;//rak[sa[i]] = i
        for(int i = 2; i <= n; i ++)
            rak[sa[i]] = (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w]) ? p : ++ p ;//此时的tp为之前的rak
    }
    for(int i = 1; i <= n; i ++)
        cout << sa[i] << " ";
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> (s + 1);
    n = strlen(s + 1);
    m = (int)'z';
    get_SA();
    return 0;
}

height数组

在后缀数组中有个强有力的工具———lcp（两个后缀的最长公共前缀）
height[i] = lcp(sa[i - 1], sa[i])
h[i] = height[rak[i]]
然后我们有个结论h[i] >= h[i- 1] - 1(证明略)
这样我们就能在O(n）的复杂度内求出height[i]

void get_HEIGHT()
{
    int k = 0;
   // for(int i = 1; i <= n; i ++)
     //   rak[sa[i]] = i;
    for(int i = 1; i <= n; i ++)
    {
        if(k)
            k --;
        int j = sa[rak[i] - 1];
        while(s[i + k] == s[j + k]) 
            k ++;
        height[rak[i]] = k;
    }
}

常见应用

求两个后缀的最长公共前缀即求lcp(i,j)
有两个性质：
$lcp(i,j)=min\left(lcp\right(i,k),lcp(k,j\left)\right)(i\&lt;=k\&lt;=j)$lcp(i,j)=min(lcp(i,k),lcp(k,j))(i<=k<=j)
$lcp(i,j)=min\left(lcp\right(k-1,k\left)\right)(i\&lt;k\&lt;=j)$lcp(i,j)=min(lcp(k−1,k))(i<k<=j)
我们发现性质二与height数组具有紧密联系，于是我们可以用rmq求解
求本质不同的所有子串 ： ${\sum }_{i=1}^n(len-sa[i]+1-height[i\left]\right)$∑i=1n​(len−sa[i]+1−height[i]) 算贡献，相交部分要减掉