后缀数组：理论与高效应用

"这篇文档是IOI2004国家集训队论文，作者许智磊，主题聚焦于后缀数组及其应用。后缀数组是字符串处理中的一个重要工具，它是后缀树的一种简洁替代，易于编程实现，占用空间少，且在某些任务上具有与后缀树相当的时间复杂度。文章涵盖了后缀数组的基本概念、构造算法、最长公共前缀的计算，以及在模式匹配和寻找最长回文子串等实际问题中的应用。" 后缀数组是一种用于处理字符串的数据结构，它存储了字符串所有后缀的排序。这里的后缀是指从某个位置开始直到字符串结尾的所有字符组成的子串。通过构建后缀数组，我们可以快速进行字符串的各种操作，如模式匹配、查找最长公共前缀等。 文章首先介绍了O(nlogn)复杂度的倍增算法来构造后缀数组。倍增算法是一种高效的排序方法，通过多次比较和调整，能在较短的时间内完成对后缀的排序。接着，为了进一步增强后缀数组的功能，文章提到了计算最长公共前缀（LCP）的方法。LCP是两个连续排列的后缀的最大公共前缀长度，它可以通过后缀数组辅助在线性时间内计算高度数组（记录跨度为1的LCP值）。 后缀数组的应用包括多模式串的模式匹配和求解最长回文子串。在多模式串的模式匹配中，后缀数组能帮助我们以O(m+logn)的时间复杂度找到所有匹配的模式，m是模式串的长度，n是主串的长度。对于寻找最长回文子串，利用后缀数组可以实现O(nlogn)的时间复杂度，这在处理大量数据时非常有效。 此外，文中还对比了后缀数组和后缀树，指出后缀数组在编程实现和空间效率上的优势，尤其是在信息学竞赛中，后缀数组更为实用。 关键词包括：字符串、后缀、k-前缀比较、后缀数组、名次数组、后缀树、倍增算法、基数排序、最长公共前缀、RMQ问题、模式匹配、回文串以及最长回文子串。 总结来说，后缀数组是一种强大的字符串处理工具，不仅能够高效地解决字符串的比较和查找问题，还能应用于复杂的问题如模式匹配和寻找回文子串，其简洁的实现和良好的性能使其在实际应用中具有很高的价值。