c++如何实现一个简单的后缀数组(Suffix Array)_c++字符串处理高级算法【源码】-C++-PHP中文网

c++如何实现一个简单的后缀数组(Suffix Array)_c++字符串处理高级算法【源码】

穿越時空

发布： 2025-12-18 02:15:26

原创

397人浏览过

c++kquote>后缀数组是字符串所有后缀按字典序排序后的起始下标数组；例如"ababa"的后缀数组为[4,0,2,1,3]；可通过暴力法（O(n²log n)）或倍增算法（O(n log²n)）构建，后者利用rank数组分轮按长度倍增排序。

c++如何实现一个简单的后缀数组(suffix array)_c++字符串处理高级算法【源码】

什么是后缀数组？

后缀数组（Suffix Array）是一个整数数组，存储字符串所有后缀按字典序排序后的起始下标。比如字符串 "ababa"，它的5个后缀是：
"ababa"（0）、"baba"（1）、"aba"（2）、"ba"（3）、"a"（4）
按字典序排序后为：
"a"(4)、"ababa"(0)、"aba"(2)、"baba"(1)、"ba"(3)
所以后缀数组 SA = [4, 0, 2, 1, 3]

暴力法：适合理解原理

对长度为 n 的字符串，生成全部 n 个后缀，用 std::sort 配合自定义比较函数排序即可。时间复杂度 O(n² log n)，适用于 n ≤ 5000 的教学或小规模场景。

关键点：
- 后缀用 std::string_view 或 substr 避免拷贝
- 比较函数直接比后缀内容（不是下标）

用 std::vector 存下标索引
用 std::iota 初始化 [0,1,...,n-1]
排序时捕获原字符串引用，避免重复构造

倍增算法：O(n log²n) 实用实现

核心思想是分轮排序：先按长度为 1 的前缀排，再按长度为 2 的前缀排，然后是 4、8……直到 ≥n。每轮用上一轮的排名作为“第一关键字”，右半段排名作为“第二关键字”，用基数排序或 std::sort 稳定排序。

简化版步骤（不写完整基数排序）：
- 维护 rank[i] 表示以 i 开头的后缀在当前长度下的排名
- 每轮构造 pair，对所有合法 i 排序
- 重新编号得到新 rank，gap *= 2

注意：
- 边界处理：i+gap 超出范围时，第二关键字设为 -1（最小）
- rank 数组可复用，用 vector> 临时存键值对

完整可运行代码（倍增 + sort 优化版）

// 编译：g++ -std=c++17 sa.cpp

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
<p>std::vector<int> build_suffix_array(const std::string& s) {
int n = s.size();
std::vector<int> sa(n), rank(n), tmp_rank(n);
for (int i = 0; i < n; ++i) {
sa[i] = i;
rank[i] = s[i];
}</p><pre class="brush:php;toolbar:false;">for (int gap = 1; gap < n; gap *= 2) {
    auto cmp = [&](int i, int j) {
        if (rank[i] != rank[j]) return rank[i] < rank[j];
        int ri = (i + gap < n) ? rank[i + gap] : -1;
        int rj = (j + gap < n) ? rank[j + gap] : -1;
        return ri < rj;
    };
    std::sort(sa.begin(), sa.end(), cmp);

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

登录后复制

}

立即学习“C++免费学习笔记（深入）”；