后缀数组通过排序字符串所有后缀实现高效字符串处理，配合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: bananai=1: ananai=2: nanai=3: anai=4: nai=5: a
排序后：
立即学习“C++免费学习笔记（深入）”；
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 #include #include using namespace std;vector buildSuffixArray(const string& s) {int n = s.size();vector sa(n), rank(n), temp(n);
// 初始化：按首字符排序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;
}
LCP数组：最长公共前缀
LCP[i] 表示后缀 SA[i] 和 SA[i-1] 的最长公共前缀长度（i ≥ 1）。LCP 数组可用于快速查询任意两个后缀的 LCP（配合 RMQ），也能帮助找出最长重复子串。
计算方法：利用 height 数组的性质，通过 SA 和 rank 数组在 O(n) 时间内求出。
LCP数组构造代码：
vector buildLCP(const string& s, const vector& sa) { int n = s.size(); vector rank(n), lcp(n); for (int i = 0; i < n; i++) rank[sa[i]] = i;int h = 0;lcp[0] = 0;for (int i = 0; i 0) { int j = sa[rank[i] - 1]; // 前一个后缀的起始位置 while (i + h < n && j + h 0) h--; }}return lcp;
}
应用示例：查找最长重复子串
利用后缀数组和 LCP 数组，LCP 数组中的最大值即为最长重复子串的长度，对应的位置可还原出具体子串。
例如，在 "banana" 中，LCP 数组为 [0,1,3,0,0,2]，最大值为 3，说明存在长度为 3 的重复子串 "ana"。
只需遍历 LCP 数组找到最大值及其位置，再用 SA[i] 取出子串即可。
基本上就这些。后缀数组结合 LCP 能高效处理很多字符串难题，虽然构造稍复杂，但一旦掌握，威力强大。
以上就是C++怎么实现一个后缀数组(Suffix Array)_C++字符串算法与LCP数组的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1487763.html
微信扫一扫 
支付宝扫一扫 
