从后缀数组构建 LCP 数组的 Kasai 算法

在我们深入探讨字符串处理的核心算法之前，让我们先回顾一下基础。后缀数组是给定字符串的所有后缀的有序数组。假设给定的字符串是 "banana"。我们将其所有后缀按字母顺序排序，就能得到一个代表字符串结构的独特视图。

正如我们在之前的文章中所讨论的，构建后缀数组通常需要 O(nLogn) 的时间。然而，仅有后缀数组往往是不够的。为了实现更高效的搜索（达到 O(m + Log n) 的复杂度），我们需要引入一个强有力的辅助工具——LCP 数组。

在2026年的今天，随着数据量的爆炸式增长和边缘计算的普及，对字符串处理算法的效率和稳定性要求达到了前所未有的高度。在这篇文章中，我们将不仅回顾 Kasai 算法的经典实现，还会融入现代 AI 辅助开发的视角，探讨如何在生产环境中编写高性能、可维护的代码。

LCP 数组：核心概念回顾

LCP 数组是一个大小为 n 的数组，其中 lcp[i] 表示后缀数组中第 i 个和第 i+1 个后缀的最长公共前缀（Longest Common Prefix）的长度。

以 "banana" 为例：

suffix[]  = {5, 3, 1, 0, 4, 2}
lcp[]     = {1, 3, 0, 0, 2, 0}

理解这个数据结构对于解决生物信息学（如 DNA 序列比对）和数据压缩等领域的复杂问题至关重要。我们需要一种高效的方法来构建它，这就是 Kasai 算法发挥作用的地方。

深入 Kasai 算法：从理论到实践

Kasai 算法的核心魔力在于它能够利用后缀数组中相邻后缀的性质，在线性时间 O(n) 内构建 LCP 数组。让我们思考一下这个场景：假设我们知道从 INLINECODE994d8b3f 开始的后缀与它的前序后缀有 k 个字符的公共前缀。那么，当我们考虑 INLINECODEc03697c5 开始的后缀时，这个公共前缀的长度至少是 k-1。这是因为我们只是去掉了第一个字符，剩下的相对顺序依然保持不变。

这种“继承”性质使得我们无需每次都从头开始比较，极大地节省了计算资源。下面，我们将展示如何在现代 C++ 环境中实现这一逻辑。

完整的 Kasai 算法 C++ 实现

在我们的生产环境中，代码的可读性和内存安全性是首要考虑因素。请注意下面代码中的注释，这通常是我们在结对编程中由 AI 助手（如 Cursor 或 Copilot）生成的解释性文档，确保团队中的每个成员都能理解算法的每一个细微差别。

#include 
using namespace std;

// 辅助函数：打印数组，用于调试和可视化
void printArray(vector& arr, string title) {
    cout << title << ": [ ";
    for (int val : arr) cout << val << " ";
    cout << "]" << endl;
}

/*
 * Kasai 算法核心实现
 * 参数:
 *   - txt: 原始文本字符串
 *   - suffixArr: 已经构建好的后缀数组
 *   - n: 字符串长度
 * 返回值:
 *   - 构建好的 LCP 数组
 * 时间复杂度: O(n)
 */
vector kasaiAlgorithm(string txt, vector suffixArr, int n) {
    // 为了加速查找，我们需要一个反向映射数组：
    // rank[i] 存储的是以 txt[i] 开头的后缀在后缀数组中的索引。
    vector rank(n, 0);
    for (int i = 0; i < n; i++)
        rank[suffixArr[i]] = i;

    vector lcp(n, 0); // 初始化 LCP 数组

    int h = 0; // h 是当前 LCP 长度的计数器

    /*
     * 遍历原始字符串的每一个后缀。
     * 这里利用了之前提到的性质：
     * 如果 txt[i] 和 txt[j] 有长度为 k 的 LCP，
     * 那么 txt[i+1] 和 txt[j+1] 的 LCP 至少是 k-1。
     */
    for (int i = 0; i  0，我们只需验证剩下的部分即可
        while (i + h < n && j + h  0) 
            h--;
    }

    // 返回结果
    return lcp;
}

2026 开发视角：代码验证与边界处理

在刚才的代码中，你可能会注意到我们没有直接跳到算法逻辑，而是先构建了 rank 数组。这是一个常见的性能陷阱。如果我们每次都对后缀数组进行二分查找来确定当前后缀的位置，复杂度将退化到 O(n Log n)。在生产级代码中，O(n) 和 O(n Log n) 在处理海量数据（如全基因组测序）时的差异是巨大的。

让我们思考一下边界情况：当处理空字符串或单字符字符串时，我们的算法是否依然健壮？在上述实现中，INLINECODE986d1c4a 循环和 INLINECODEc4930d1d 循环的条件判断 i + h < n 确保了不会发生越界访问。这正是我们在编写安全关键型代码时所必须具备的严谨态度。

现代 C++ 构建完整示例

为了让你能够直观地运行和理解这个过程，我们提供了一个完整的、包含后缀数组构建（简化版）和 LCP 构建的示例。在我们的最近的项目中，我们习惯于将这种算法封装成通用的库，以便在不同的微服务中复用。

// 完整的构建与测试示例
#include 
#include 
#include 
#include 

using namespace std;

// 结构体用于后缀排序
struct Suffix {
    int index;
    int rank[2];
};

// 比较函数，用于排序
int cmp(struct Suffix a, struct Suffix b) {
    return (a.rank[0] == b.rank[0]) ? (a.rank[1] < b.rank[1] ? 1 : 0) :
           (a.rank[0] < b.rank[0] ? 1 : 0);
}

// 构建后缀数组 (O(nLogn) 方法)
vector buildSuffixArray(string s, int n) {
    struct Suffix suffixes[n];

    for (int i = 0; i < n; i++) {
        suffixes[i].index = i;
        suffixes[i].rank[0] = s[i] - 'a';
        suffixes[i].rank[1] = ((i + 1) < n) ? (s[i + 1] - 'a') : -1;
    }

    sort(suffixes, suffixes + n, cmp);

    int ind[n];
    for (int k = 4; k < 2 * n; k = k * 2) {
        int rank = 0;
        int prev_rank = suffixes[0].rank[0];
        suffixes[0].rank[0] = rank;
        ind[suffixes[0].index] = 0;

        for (int i = 1; i < n; i++) {
            if (suffixes[i].rank[0] == prev_rank &&
                suffixes[i].rank[1] == suffixes[i - 1].rank[1]) {
                prev_rank = suffixes[i].rank[0];
                suffixes[i].rank[0] = rank;
            } else {
                prev_rank = suffixes[i].rank[0];
                suffixes[i].rank[0] = ++rank;
            }
            ind[suffixes[i].index] = i;
        }

        for (int i = 0; i < n; i++) {
            int nextindex = suffixes[i].index + k / 2;
            suffixes[i].rank[1] = (nextindex < n) ?
                                  suffixes[ind[nextindex]].rank[0] : -1;
        }

        sort(suffixes, suffixes + n, cmp);
    }

    vector suffixArr;
    for (int i = 0; i < n; i++)
        suffixArr.push_back(suffixes[i].index);

    return suffixArr;
}

// 这里插入上面实现的 kasaiAlgorithm 函数
// ... (kasaiAlgorithm 代码见上文) ...

int main() {
    string txt = "banana";
    cout << "输入字符串: " << txt << endl;
    
    // 1. 构建后缀数组
    vector suffixArr = buildSuffixArray(txt, txt.length());
    cout << "后缀数组: ";
    for(int i : suffixArr) cout << i << " ";
    cout << endl;

    // 2. 构建 LCP 数组
    vector lcp = kasaiAlgorithm(txt, suffixArr, txt.length());
    cout << "LCP 数组: ";
    for(int i : lcp) cout << i << " ";
    cout << endl;

    return 0;
}

从 AI 原生视角看算法选择

随着我们步入 2026 年，AI 辅助编程已经从“锦上添花”变成了“必不可少”。我们在使用 Cursor 或 GitHub Copilot 等 AI IDE 时，不仅要让 AI 帮我们写代码，更要让它成为我们的架构审查员。

例如，当我们实现 Kasai 算法时，AI 可以帮助我们验证边界条件。如果你问 AI：“这个实现是否考虑了 Unicode 多字节字符？”它可能会指出当前实现基于 char，仅适用于 ASCII。在全球化应用中，我们需要考虑 UTF-8 编码，这可能会改变我们计算索引的方式。这是一个很好的例子，展示了基础算法如何在实际工程场景中演变。

性能优化与可观测性

在现代云原生架构中，我们将计算推向边缘。这意味着算法不仅要快，还要内存占用小。Kasai 算法的一个优点是它不需要像 Manber & Myers 算法那样在构建过程中维护复杂的树结构，因此它的缓存命中率更高。

我们建议在代码中植入可观测性点。比如，在处理超长字符串时，可以记录 INLINECODE52f28f19 值的变化趋势。如果发现 INLINECODE6b37f511 值普遍很高，说明字符串的重复性很高，这也许是启用特定压缩算法（如 LZW）的好时机。这种数据驱动的优化思维，是现代后端工程师必备的素质。

常见陷阱与替代方案

在我们的实战经验中，新手在使用 Kasai 算法时常犯的一个错误是在构建 INLINECODEd057848b 数组时出错。记住，INLINECODE0dab0fbb 数组是连接原始字符串索引和后缀数组索引的桥梁。如果这里的映射关系弄反了，LCP 数组的计算结果将完全错误。

此外，Kasai 算法依赖于已经构建好的后缀数组。如果你需要同时构建两者，目前的做法是分两步走。但在学术界，也存在一些诱导式算法可以同步生成。然而，在工程实践中，为了模块化和可测试性，我们通常更倾向于 Kasai 这种清晰的分步方法。

总结

通过这篇文章，我们不仅重新审视了经典的 Kasai 算法，更重要的是，我们模拟了一次现代软件开发的流程：从算法原理理解，到编码实现，再到边界检查和性能考量。在 AI 赋能的时代，掌握这些基础算法，并结合现代工程理念进行落地，将使我们能够构建出更加健壮、高效的系统。希望你在阅读这篇文章后，不仅学会了“怎么做”，还理解了“为什么这么做”以及“如何在 2026 年做得更好”。