C++怎么实现一个后缀数组(Suffix Array)_C++字符串算法与LCP数组

新闻中心 NEWS CENTER

您当前位置：首页 > 新闻中心 > 网络学院

C++怎么实现一个后缀数组(Suffix Array)_C++字符串算法与LCP数组

2025-12-04

浏览次数：次

返回列表

后缀数组通过排序字符串所有后缀实现高效字符串处理，配合LCP数组可快速求解最长重复子串等问题。

c++怎么实现一个后缀数组(suffix array)_c++字符串算法与lcp数组

后缀数组（Suffix Array）是处理字符串问题的重要工具，常用于查找最长重复子串、最长回文子串、字符串匹配等场景。它通过对字符串的所有后缀进行排序，得到一个按字典序排列的后缀索引数组。配合LCP（Longest Common Prefix）数组，可以高效解决多种字符串问题。

后缀数组的基本概念

给定一个字符串 S[0..n-1]，它的后缀是指从某个位置开始到末尾的子串，即 S[i..n-1]。后缀数组 SA[0..n-1] 是一个整数数组，保存的是使得所有后缀 S[SA[i]..n-1] 按字典序升序排列的起始下标。

例如，S = "banana"，其所有后缀为：

i=0: banana
i=1: anana
i=2: nana
i=3: ana
i=4: na
i=5: a

排序后：

a (i=5)
ana (i=3)
anana (i=1)
banana (i=0)
na (i=4)
nana (i=2)

所以 SA = [5, 3, 1, 0, 4, 2]

构造后缀数组：倍增法（Doubling Method）

直接对每个后缀排序时间复杂度为 O(n²logn)，效率低。我们可以使用倍增法在 O(n log n) 时间内完成构造。

核心思想：按长度 1, 2, 4, 8... 的前缀对后缀排序，每次利用上一次排序的结果进行快速比较。

步骤如下：

初始化：对每个字符排序，得到初始排名 rank[0..n-1]
倍增：对于 k = 1, 2, 4, ..., 将每个后缀的排名表示为 pair(rank[i], rank[i+k])
重新排序这些 pair，并更新 rank 数组
当所有 rank 值唯一时停止

代码实现：

#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
<p>vector<int> buildSuffixArray(const string& s) {
int n = s.size();
vector<int> sa(n), rank(n), temp(n);</p><pre class='brush:php;toolbar:false;'>// 初始化：按首字符排序
for (int i = 0; i < n; i++) {
    sa[i] = i;
    rank[i] = s[i];
}

for (int k = 1; k < n; k *= 2) {
    auto cmp = [&](int i, int j) {
        if (rank[i] != rank[j])
            return rank[i] < rank[j];
        int ri = (i + k < n) ? rank[i + k] : -1;
        int rj = (j + k < n) ? rank[j + k] : -1;
        return ri < rj;
    };
    sort(sa.begin(), sa.end(), cmp);

    temp[sa[0]] = 0;
    for (int i = 1; i < n; i++) {
        temp[sa[i]] = temp[sa[i-1]] + (cmp(sa[i-1], sa[i]) ? 1 : 0);
    }
    rank = temp;
}
return sa;

}

Tunee AI

新一代AI音乐智能体

1104 查看详情 Tunee AI

LCP数组：最长公共前缀

LCP[i] 表示后缀 SA[i] 和 SA[i-1] 的最长公共前缀长度（i ≥ 1）。LCP 数组可用于快速查询任意两个后缀的 LCP（配合 RMQ），也能帮助找出最长重复子串。

计算方法：利用 height 数组的性质，通过 SA 和 rank 数组在 O(n) 时间内求出。

LCP数组构造代码：

vector<int> buildLCP(const string& s, const vector<int>& sa) {
    int n = s.size();
    vector<int> rank(n), lcp(n);
    for (int i = 0; i < n; i++)
        rank[sa[i]] = i;
<pre class='brush:php;toolbar:false;'>int h = 0;
lcp[0] = 0;
for (int i = 0; i < n; i++) {
    if (rank[i] > 0) {
        int j = sa[rank[i] - 1]; // 前一个后缀的起始位置
        while (i + h < n && j + h < n && s[i+h] == s[j+h])
            h++;
        lcp[rank[i]] = h;
        if (h > 0) h--;
    }
}
return lcp;