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

后缀数组通过排序字符串所有后缀实现高效字符串处理，配合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);</int></int></p>
<pre class="brush:php;toolbar:false;">// 初始化：按首字符排序
for (int i = 0; i <p>}</p><div class="aritcle_card flexRow artxards">
											<div class="artcardd flexRow">
												<a class="aritcle_card_img" rel="nofollow" href="/xiazai/gongju/2823" title="C++14"><img
														src="https://img.php.cn/upload/manual/001/431/639/6ac8b33c327c4749.png" alt="C++14" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
												<div class="aritcle_card_info flexColumn">
													<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="overflowclass">C++14</a>
													<p class="overflowclass">C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。</p>
												</div>
												<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
												</a>
											</div>
										</div>

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 int h = 0;
lcp[0] = 0;
for (int i = 0; i  0) {
        int j = sa[rank[i] - 1]; // 前一个后缀的起始位置
        while (i + h  0) h--;
    }
}
return lcp;</int></int></int>

}