后缀数组：后缀数组是什么？解决字符串问题的利器

后缀数组是对字符串所有后缀按字典序排序后，存储排序后缀起始位置的数组。后缀指从字符串每个位置开始到末尾的子串（如“banana”的后缀有“banana”“anana”等）。字典序比较规则为：首字符不同则按字符大小比较，相同则依次比较后续字符，若一后缀是另一前缀则较短的更小。 以“abrac”为例，其后缀排序后起始位置数组为[0,3,4,1,2]（如位置0的“abrac”<位置3的“ac”，再依次排列）。 后缀数组的核心价值在于高效解决字符串问题：通过排序后相邻后缀的紧密关系（公共前缀长），可快速处理最长重复子串、子串存在性等。例如，用LCP数组找最长重复子串，或通过二分查找验证子串是否存在。 总结：后缀数组通过排序后缀起始位置，为字符串问题提供高效解决方案，是字符串处理的实用工具。