快速构建与搜索：Suffix Arrays 算法综述

"Suffix Arrays是字符串处理中的一个重要概念，由U. Manber和G. Myers在1993年提出，随后J. Karkkainen和P. Sanders在2002年提出了线性时间复杂度的构建方法。后缀数组是一种用于在线字符串搜索的数据结构，它提供了一种更简单、更高效的方式来处理字符串的搜索问题，特别是对比于需要大量空间的后缀树。通过后缀数组，可以在O(P + log N)的时间复杂度内查找一个长度为P的子串在长度为N的字符串中的所有出现位置。" 在1993年，Manber和Myers引入了后缀数组的概念，这是一种在线字符串搜索的新方法。后缀数组是一个有序的字符串后缀集合，由指向字符串S各个后缀的指针组成。例如，对于字符串S = "nahariya"，其后缀数组将包括排序后的所有后缀，如"yahariya"、"hariya"等，这些后缀由数组中的整数（表示每个后缀在原始字符串中的起始位置）来表示。 传统的后缀树虽然提供了很多功能，但其线性空间复杂度是其主要缺点。相对而言，后缀数组提供了更简洁的数据结构。通过后缀数组，我们可以在O(P + log N)的时间复杂度内完成搜索，这里的P是目标子串的长度，N是原始字符串的长度。这类似于二分查找的过程，可以快速定位到目标子串的所有出现位置。 1993年的构建方法基于排序和LCP（Longest Common Prefix，最长公共前缀）信息的构建。排序是构建后缀数组的基础，通过对后缀进行比较排序，得到后缀数组。接着，LCP信息的计算可以帮助进一步优化搜索效率，它揭示了相邻后缀之间的关系。 然而，直到2002年，J. Karkkainen和P. Sanders提出了一种改进的构建方法，将构建后缀数组的时间复杂度降低到了线性时间O(n)。这一突破性的进展使得后缀数组在实际应用中更具优势，尤其是在处理大规模文本数据时，能够快速、高效地进行字符串搜索。 总结来说，后缀数组是一个强大的工具，特别适用于字符串搜索和模式匹配任务。它克服了后缀树的空间复杂度问题，同时保持了高效的查询性能。2002年提出的线性时间复杂度构造算法更是大大提升了其实用性，使得后缀数组在生物信息学、文本分析、数据挖掘等多个领域得到了广泛应用。