在很多场合下能够代替 SAM 的算法：对 height 数组建立笛卡尔树

szh_AK_all · 2025-04-07 12:47:05 · 算法·理论

其实这是一篇学习笔记。

阅读本文需要一定的后缀数组及单调栈基础。

有关后缀数组的常用知识点

一般的，设 sa_i 表示字典序第 i 小的后缀的起始位置，rk_i 表示起始位置为 i 的后缀的字典序排名，h_i 表示字典序第 i 小的与字典序第 i+1 小（当然也可能是 i-1，习惯问题）的后缀的最长公共前缀。则有：rk_{sa_i}=i，h_i\ge h_{i-1}-1。并且排名为 i 的后缀与排名为 j 的后缀的 LCP=\min_{k=i}^{j-1} h_k

而有关子串的问题也常常和后缀结合起来，因为字符串的子串可以看成是该字符串的某个后缀的一段前缀，最经典的问题就是求一个字符串的本质不同子串个数。考虑每两个字典序排名相邻的后缀本质相同的前缀个数其实就是 h，所以一个字符串 s 的本质不同后缀个数就是 \frac{n\times (n+1)}{2}-\sum h。

关于 height 数组——引出笛卡尔树

在很多情况下，我们需要考虑每对 (i,j)，并对起始位置分别为 i,j 的后缀进行分析。如果分析时涉及到两后缀的 LCP，那么我们会很自然的想到他们的 LCP=\min_{k=i}^{j-1} h_k。如果从每个 h_k 对所有 (i,j) 产生的影响的角度考虑呢？也就是什么样的 (i,j) 满足起始位置分别为 i,j 的后缀的 LCP=h_k？再结合上面的式子显然可以发现满足这个条件当且仅当 \min_{l=i}^{j-1}h_l =h_k。也就是说 h_k 是 h_{i\sim j-1} 中的最小值。

这个问题是不是很可以用笛卡尔树来解决啊！考虑对 height 建立笛卡尔树，那么在建树之后，对于一个节点 x，他的左右子树内的所有 h 值都不低于 h_x，也就是说从左右子树所代表的后缀范围内各任选一个后缀，他们的 LCP=h_x。

显然 h_n=0，而 h_n 本身是无意义的，所以我们可以从它下手，让他作为笛卡尔树的根，所以需要强制令 h_n=-1。那么他的左儿子即对应了 h_{1\sim n-1} 中的最小值，而这个最小值所在的位置可以看做是笛卡尔树的真正的根。

在笛卡尔树上，每个节点 x 代表着字典序第 x 小的后缀，也相当于是 h 数组的某个下标。而每个节点都对应着一个实际的影响区间，假设它是 h_{l\sim r} 中的最小值（显然有 l\le x\le r），那么它的影响区间就是 l\sim r+1，也就是说它及它的子树包含着字典序第 l\sim r+1 小的后缀（因为 h_i 表示的是字典序第 i 小与第 i+1 小的后缀的 LCP）。

所以对于一个节点 x，若他的影响区间为 l\sim r，则他的左儿子的影响区间为 l\sim x（左儿子 h 为 h_{l\sim x-1} 中的最小值，所以左儿子的影响区间为 l\sim x），右儿子的影响区间即为 x+1\sim r。

下面举个例子：

模版代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000005;
int a[N], b[N], sa[N], h[N], rk[N], t[N], q[N];
string s;
int n, m;

void getsa() {
    memset(t, 0, sizeof(t));
    memset(sa, 0, sizeof(sa));
    for (int i = 1; i <= n; i++) {
        a[i] = s[i];
        ++t[a[i]];
    }
    for (int i = 2; i <= 128; i++)
        t[i] += t[i - 1];
    for (int i = n; i >= 1; i--)
        sa[t[a[i]]--] = i;
    int now = 128;
    for (int k = 1; k <= n; k *= 2) {
        int cnt = 0;
        for (int i = n - k + 1; i <= n; i++)
            b[++cnt] = i;
        for (int i = 1; i <= n; i++)
            if (sa[i] > k)
                b[++cnt] = sa[i] - k;
        memset(t, 0, sizeof(t));
        for (int i = 1; i <= n; i++)
            t[a[i]]++;
        for (int i = 2; i <= now; i++)
            t[i] += t[i - 1];
        for (int i = n; i >= 1; i--)
            sa[t[a[b[i]]]--] = b[i], b[i] = 0;
        swap(a, b);
        int tot = 1;
        a[sa[1]] = 1;
        for (int i = 2; i <= n; i++) {
            if (b[sa[i]] == b[sa[i - 1]] && b[sa[i] + k] == b[sa[i - 1] + k])
                a[sa[i]] = tot;
            else
                a[sa[i]] = ++tot;
        }
        if (tot == n)
            break;
        now = tot;
    }
}

void gethi() {
    memset(rk, 0, sizeof(rk));
    memset(h, 0, sizeof(h));
    for (int i = 1; i <= n; i++)
        rk[sa[i]] = i;
    int now = 0;
    for (int i = 1; i <= n; i++) {
        if (rk[i] == 1)
            continue;
        if (now)
            now--;
        int j = sa[rk[i] - 1];
        while (i + now <= n && j + now <= n && s[i + now] == s[j + now])
            now++;
        h[rk[i]] = now;
    }
    for (int i = 1; i <= n; i++)
        h[i] = h[i + 1];
}

struct node {
    int l, r, hi;
    int ql, qr;
} p[N];

void bu(int d, int l, int r) {
    if (!d)
        return;
    p[d].ql = l, p[d].qr = r;
    bu(p[d].l, l, d);
    bu(p[d].r, d + 1, r);
}
int qq[N];

void dikaer() {
    int top = 0;
    h[n] = -1;
    for (int i = 1; i <= n; i++) {
        int now = 0;
        while (top && h[i] <= h[qq[top]]) {
            p[qq[top]].r = now;
            now = qq[top];
            top--;
        }
        p[i].l = now;
        qq[++top] = i;
    }
}
int ans;

void dfs(int x) {
    if (p[x].l)
        dfs(p[x].l);
    if (p[x].r)
        dfs(p[x].r);
    //做一些事情
}
signed main() {
    cin >> s;
    n = s.size();
    s = " " + s;
    getsa();
    gethi();
    dikaer();
    bu(p[n].l, 1, n);
    dfs(p[n].l);
}

例题

P3804 【模板】后缀自动机（SAM）

首先对 height 数组建出笛卡尔树。

注意到每个子串可以表示成原串的某个后缀的一段前缀，观察题目要求，出现次数不为 1 即代表符合要求的子串应当是某两个后缀的公共前缀，而为了子串长度尽可能长，所以他应当是某两个后缀的 LCP。那么可以考虑树上每个节点所产生的子串。

对于一个节点 x，从它的左右区间所涵盖的后缀范围内各任选一个后缀，则他们的 LCP=h_x，那么考虑这个公共前缀的出现次数，显然是 x 的影响区间的长度，或者说是他及其子树所涵盖的后缀的数量，假设其为 y，那么用 h_x\times y 更新答案即可。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000005;
int a[N], b[N], sa[N], h[N], rk[N], t[N], q[N];
string s;
int n, m;

void getsa() {
    memset(t, 0, sizeof(t));
    memset(sa, 0, sizeof(sa));
    for (int i = 1; i <= n; i++) {
        a[i] = s[i];
        ++t[a[i]];
    }
    for (int i = 2; i <= 128; i++)
        t[i] += t[i - 1];
    for (int i = n; i >= 1; i--)
        sa[t[a[i]]--] = i;
    int now = 128;
    for (int k = 1; k <= n; k *= 2) {
        int cnt = 0;
        for (int i = n - k + 1; i <= n; i++)
            b[++cnt] = i;
        for (int i = 1; i <= n; i++)
            if (sa[i] > k)
                b[++cnt] = sa[i] - k;
        memset(t, 0, sizeof(t));
        for (int i = 1; i <= n; i++)
            t[a[i]]++;
        for (int i = 2; i <= now; i++)
            t[i] += t[i - 1];
        for (int i = n; i >= 1; i--)
            sa[t[a[b[i]]]--] = b[i], b[i] = 0;
        swap(a, b);
        int tot = 1;
        a[sa[1]] = 1;
        for (int i = 2; i <= n; i++) {
            if (b[sa[i]] == b[sa[i - 1]] && b[sa[i] + k] == b[sa[i - 1] + k])
                a[sa[i]] = tot;
            else
                a[sa[i]] = ++tot;
        }
        if (tot == n)
            break;
        now = tot;
    }
}

void gethi() {
    memset(rk, 0, sizeof(rk));
    memset(h, 0, sizeof(h));
    for (int i = 1; i <= n; i++)
        rk[sa[i]] = i;
    int now = 0;
    for (int i = 1; i <= n; i++) {
        if (rk[i] == 1)
            continue;
        if (now)
            now--;
        int j = sa[rk[i] - 1];
        while (i + now <= n && j + now <= n && s[i + now] == s[j + now])
            now++;
        h[rk[i]] = now;
    }
    for (int i = 1; i <= n; i++)
        h[i] = h[i + 1];
}

struct node {
    int l, r, hi;
    int ql, qr;
} p[N];

void bu(int d, int l, int r) {
    if (!d)
        return;
    p[d].ql = l, p[d].qr = r;
    bu(p[d].l, l, d);
    bu(p[d].r, d + 1, r);
}
int qq[N];

void dikaer() {
    int top = 0;
    h[n] = -1;
    for (int i = 1; i <= n; i++) {
        int now = 0;
        while (top && h[i] <= h[qq[top]]) {
            p[qq[top]].r = now;
            now = qq[top];
            top--;
        }
        p[i].l = now;
        qq[++top] = i;
    }
}
int ans;

void dfs(int x) {
    if (p[x].l)
        dfs(p[x].l);
    if (p[x].r)
        dfs(p[x].r);
    ans = max(ans, h[x] * (p[x].qr - p[x].ql + 1));
}

signed main() {
    cin >> s;
    n = s.size();
    s = " " + s;
    getsa();
    gethi();
    dikaer();
    bu(p[n].l, 1, n);
    dfs(p[n].l);
    cout << ans;
}

SP10079 STAMMER - Stammering Aliens

还是先建出笛卡尔树，题目要求出现次数不低于 m 且长度最长最靠右的子串，那么对于出现次数这个条件，我们仍然考虑枚举每个节点，只有它所代表的左右子树的 LCP 才可能是答案，而这个 LCP 的出现次数即为当前节点的影响区间，那么我们可以以此来更新答案。

当然我们还需要求每个节点所代表的左右子树的 LCP 最后出现的位置，也就是该节点及其子树所涵盖的起始位置最大的后缀，这个可以用 maxn 来记录。对于一个节点 x，在遍历完他的左右子树 l,r 后，便可以用 maxn_l,maxn_r 来更新 maxn_x。而 maxn_x 的初始值是 \max(sa_x,sa_{x+1})（这个地方很容易错！）。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 40005;
int a[N], b[N], sa[N], h[N], rk[N], t[N], q[N];
string s;
int n, m;

void getsa() {
    memset(t, 0, sizeof(t));
    memset(sa, 0, sizeof(sa));
    for (int i = 1; i <= n; i++) {
        a[i] = s[i];
        ++t[a[i]];
    }
    for (int i = 2; i <= 128; i++)
        t[i] += t[i - 1];
    for (int i = n; i >= 1; i--)
        sa[t[a[i]]--] = i;
    int now = 128;
    for (int k = 1; k <= n; k *= 2) {
        int cnt = 0;
        for (int i = n - k + 1; i <= n; i++)
            b[++cnt] = i;
        for (int i = 1; i <= n; i++)
            if (sa[i] > k)
                b[++cnt] = sa[i] - k;
        memset(t, 0, sizeof(t));
        for (int i = 1; i <= n; i++)
            t[a[i]]++;
        for (int i = 2; i <= now; i++)
            t[i] += t[i - 1];
        for (int i = n; i >= 1; i--)
            sa[t[a[b[i]]]--] = b[i], b[i] = 0;
        swap(a, b);
        int tot = 1;
        a[sa[1]] = 1;
        for (int i = 2; i <= n; i++) {
            if (b[sa[i]] == b[sa[i - 1]] && b[sa[i] + k] == b[sa[i - 1] + k])
                a[sa[i]] = tot;
            else
                a[sa[i]] = ++tot;
        }
        if (tot == n)
            break;
        now = tot;
    }
}

void gethi() {
    memset(rk, 0, sizeof(rk));
    memset(h, 0, sizeof(h));
    for (int i = 1; i <= n; i++)
        rk[sa[i]] = i;
    int now = 0;
    for (int i = 1; i <= n; i++) {
        if (rk[i] == 1)
            continue;
        if (now)
            now--;
        int j = sa[rk[i] - 1];
        while (i + now <= n && j + now <= n && s[i + now] == s[j + now])
            now++;
        h[rk[i]] = now;
    }
    for (int i = 1; i <= n; i++)
        h[i] = h[i + 1];
}

struct node {
    int l, r, hi;
    int ql, qr;
} p[N];

void bu(int d, int l, int r) {
    if (!d)
        return;
    p[d].ql = l, p[d].qr = r;
    bu(p[d].l, l, d);
    bu(p[d].r, d + 1, r);
}
int qq[N];

void dikaer() {
    int top = 0;
    h[n] = -1;
    for (int i = 1; i <= n; i++) {
        int now = 0;
        while (top && h[i] <= h[qq[top]]) {
            p[qq[top]].r = now;
            now = qq[top];
            top--;
        }
        p[i].l = now;
        qq[++top] = i;
    }
}
int ans, wei = -1, maxn[N];

void dfs(int x) {
    maxn[x] = max(sa[x], sa[x + 1]);
    if (p[x].l)
        dfs(p[x].l);
    if (p[x].r)
        dfs(p[x].r);
    maxn[x] = max(maxn[x], max(maxn[p[x].l], maxn[p[x].r]));
    if (p[x].qr - p[x].ql + 1 >= m && h[x] != 0) {
        if (h[x] > ans || (h[x] == ans && maxn[x] > wei)) {
            ans = h[x];
            wei = maxn[x];
        }
    }
}

signed main() {
    while (1) {
        cin >> m;
        if (!m)
            return 0;
        cin >> s;
        n = s.size();
        s = " " + s;
        if (m == 1) {
            cout << n << " " << 0 << "\n";
            continue;
        }
        getsa();
        gethi();
        dikaer();
        bu(p[n].l, 1, n);
        dfs(p[n].l);
        if (wei == -1)
            cout << "none\n";
        else
            cout << ans << " " << wei - 1 << "\n";
        ans = 0;
        wei = -1;
        memset(p, 0, sizeof(p));
        memset(maxn, 0, sizeof(maxn));
        memset(qq, 0, sizeof(qq));
    }
}

P5115 Check,Check,Check one two!

记 f_x=\sum_{l=1}^{k_1} \sum_{r=1}^{k_2}[l+r-1=x]\times l\times r，则我们要求的式子可以转化成 \sum_{i=1}^n \sum_{j=i+1}^n [s_{i-1}\ne s_{j-1}]\times f_{lcp(rk_i,rk_j)}，转而枚举 lcp(rk_i,rk_j)，即 \sum_{i=1}^n f_i\times \sum_{i=1}^n \sum_{j=i+1}^n [lcp(rk_i,rk_j)=k]\times [s_{i-1}\ne s_{j-1}]，也就是 \sum_{i=1}^n f_i\times \sum_{i=1}^n \sum_{j=i+1}^n[lcp(i,j)=k]\times [s_{sa_i-1}\ne s_{sa_j-1}]。

那么可以考虑枚举每个 lcp 计算其对答案的贡献。

我们仍然可以对 height 数组建出笛卡尔树，对于当前点 x，从它的左右区间所涵盖的后缀范围内各任选一个后缀，则他们的 lcp=h_x。但是我们从左右子树选出节点 i,j 后，还需满足 s_{sa_i-1}\ne s_{sa_j-1}，显然某个 s_k 只有 26 种取值，于是可以设 g_{i,j} 表示在节点 i 的子树中满足 sa_{sa_y-1}=j 的 y 的个数。转移有 g_{x,i}=g_{lson,i}+g_{rson,i}，对答案的贡献为 \sum_{i\ne j} g_{lson,i}\times g_{rson,j}，这个是好算的。

考虑计算 f_x。