定义

$SA$排名为$i$的后缀的位置
$rk$位置为$i$的后缀的排名
$tp$第二关键字的排名为$i$的后缀的位置，还被用作$rank$的暂存
$tax$每个排名对应的后缀数量
后缀数组就是为了求出$sa$和$rk$

性质

$rk[sa[i]]=i$ $sa[rk[i]]=i$

$LCP(x,y) $：字符串x与字符串y的最长公共前缀，在这里指x号后缀与与y号后缀的最长公共前缀

$height[i]=lcp ( sa[i],sa[i - 1] )$，即排名为$i$的后缀与排名为$i−1$的后缀的最长公共前缀

$H[i]：height[rak[i]]$，即$i$号后缀与它前一名的后缀的最长公共前缀

$H[i] \geqslant H[i - 1] - 1$ 证明

$LCP(i,j)=LCP(j,i) $

$LCP(i,i)=len(sa[i])=n-sa[i]+1$

$LCP(i,k)=min\left{height[j] \right}(i+1<=j<=k)$

$S$不同的子串个数$\dfrac{n(n+1)}{2} -\sum_{i=1}^nheight[i]$

代码

#include <iostream> 
#include <cstdio>
#include <string>
#define R register int

using namespace std;
const int N = 1000005;
string s;
/* sa[i]：排名为i的后缀的位置
rak[i]：从第i个位置开始的后缀的排名，下文为了叙述方便，把从第i个位置开始的后缀简称为后缀i
tp[i]：基数排序的第二关键字，意义与sa一样，即第二关键字排名为i的后缀的位置
tax[i]：i号元素出现了多少次。辅助基数排序
s：字符串，s[i]表示字符串中第i个字符串*/
int n, m, sa[N], rk[N], tp[N], c[N];
void _sort() {
    for(R i = 1; i <= m; ++i) c[i] = 0;
    for(R i = 1; i <= n; ++i) c[rk[i]]++;
    for(R i = 1; i <= m; ++i) c[i] += c[i - 1];
    for(R i = n; i >= 1; --i) sa[c[rk[tp[i]]]--] = tp[i];
}
void SA() {
    m = 150;
    for(R i = 1; i <= n; ++i) rk[i] = s[i - 1], tp[i] = i;
    _sort();
    for(R w = 1, p = 0; p < n && w <= n; m = p, w <<= 1) {
        p = 0;
        for(R i = 1; i <= w; ++i) tp[++p] = n - w + i;
        for(R i = 1; i <= n; ++i) if(sa[i] > w) tp[++p] = sa[i] - w;
        _sort();
        swap(tp, rk);
        rk[sa[1]] = p = 1;
        for(R i = 2; i <= n; ++i)
            rk[sa[i]] = (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w])
            ? p : ++p;
    }
}
/*i号后缀：从i开始的后缀
lcp(x,y)：字符串x与字符串y的最长公共前缀，在这里指x号后缀与与y号后缀的最长公共前缀
height[i]：lcp(sa[i],sa[i-1])，即排名为i的后缀与排名为i-1的后缀的最长公共前缀
H[i]：height[rak[i]]，即i号后缀与它前一名的后缀的最长公共前缀*/
int Height[N];
void Get() {
    int j, k = 0;
    for(int i = 1; i <= n; i++) {
        if(k) k--;
        j = sa[rk[i] - 1];
        while(s[i + k - 1] == s[j + k - 1]) ++k;
        Height[rk[i]] = k;
    }
}
int main()
{
    cin >> s;
    n = s.length();
    SA();
    for(R i = 1; i <= n; ++i) printf("%d ", sa[i]);
    cout << endl;
    Get();
    return 0;
}

Problem

P2408 不同子串个数

$ans=\dfrac{n(n+1)}{2}-\sum height[i]$

#include <iostream> 
#include <cstdio>
#include <string>
#define R register int

using namespace std;
const int N = 1000005;
string s;
int n, m, sa[N], rk[N], tp[N], c[N];
void _sort() {
    for(R i = 1; i <= m; ++i) c[i] = 0;
    for(R i = 1; i <= n; ++i) c[rk[i]]++;
    for(R i = 1; i <= m; ++i) c[i] += c[i - 1];
    for(R i = n; i >= 1; --i) sa[c[rk[tp[i]]]--] = tp[i];
}
void SA() {
    m = 150;
    for(R i = 1; i <= n; ++i) rk[i] = s[i - 1], tp[i] = i;
    _sort();
    for(R w = 1, p = 0; p < n && w <= n; m = p, w <<= 1) {
        p = 0;
        for(R i = 1; i <= w; ++i) tp[++p] = n - w + i;
        for(R i = 1; i <= n; ++i) if(sa[i] > w) tp[++p] = sa[i] - w;
        _sort();
        swap(tp, rk);
        rk[sa[1]] = p = 1;
        for(R i = 2; i <= n; ++i)
            rk[sa[i]] = (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w])
            ? p : ++p;
    }
}
int Height[N];//H[i] = Height[rk[i]]
void Get() {
    int j, k = 0;
    for(int i = 1; i <= n; ++i) {
        if(k) k--;
        j = sa[rk[i] - 1];
        while(s[i + k - 1] == s[j + k - 1]) ++k;
        Height[rk[i]] = k;
    }
}
int main()
{
    cin >> n >> s;
    SA();
    Get();
    long long ans = 1LL * n * (n + 1) / 2;
    for(int i = 1; i <= n; ++i)
        ans -= Height[rk[i]];
    cout << ans << endl;
    return 0;
}

本文由落影汐雾原创，采用保留署名-非商业性使用-禁止演绎 4.0-国际许可协议
本文链接：https://x.lyxw.xyz/2019/SA/