后缀数组是什么？我们先从“后缀”说起。对于一个字符串，比如“banana”，它的后缀是从每个位置开始到末尾的子串：
- 位置0：banana（整个字符串）
- 位置1：anana
- 位置2：nana
- 位置3：ana
- 位置4：na
- 位置5：a
这些后缀中，每个后缀都有一个起始位置（比如“banana”的起始位置是0）。现在，如果我们把这些后缀按照字典序（就是我们平时查字典的顺序）从小到大排序，得到的结果就可以叫做“后缀数组”。不过在实际应用中，后缀数组通常不直接存储后缀本身，而是存储这些后缀的起始位置，因为直接存后缀会占用太多空间。
举个更简单的例子，假设字符串是“abrac”，它的索引是0到4：
- 位置0：a b r a c → 后缀：abrac
- 位置1：b r a c → 后缀：brac
- 位置2：r a c → 后缀：rac
- 位置3：a c → 后缀：ac
- 位置4：c → 后缀：c
现在我们要把这些后缀按字典序排序。字典序的比较规则是：先比较第一个字符，如果不同，谁的第一个字符小，谁就小；如果第一个字符相同，就比较第二个字符，以此类推。如果一个后缀是另一个后缀的前缀，那么较短的那个更小。
逐个比较这些后缀：
- 以“a”开头的有两个：位置0的“abrac”和位置3的“ac”。比较第二个字符：“abrac”的第二个字符是“b”，“ac”的第二个字符是“c”。因为“b” < “c”，所以“abrac” < “ac”，因此“abrac”排在“ac”前面。
- 接下来是“b”开头的“brac”（位置1），然后是“c”开头的“c”（位置4），最后是“r”开头的“rac”（位置2）。
所以排序后的顺序是：“abrac”（0）、“ac”（3）、“c”（4）、“brac”（1）、“rac”（2）。因此，这个字符串的后缀数组就是存储这些起始位置的数组：[0, 3, 4, 1, 2]。
为什么后缀数组有用呢？想象一下，如果我们要解决“字符串中最长的重复子串是什么”或者“某个子串是否存在”这样的问题。如果不使用后缀数组，直接比较所有可能的子串会非常耗时，尤其是对于长字符串。而后缀数组通过对所有后缀排序，相邻的后缀之间往往有更紧密的关系（比如它们的公共前缀可能更长），这使得我们可以用更高效的方法解决这些问题。
比如，在后缀数组中，相邻的两个后缀的最长公共前缀（LCP）可以帮助我们找到原字符串中最长的重复子串。或者，如果我们想知道某个子串是否存在，只需要在排序后的后缀数组中，通过二分查找对应的起始位置，就能快速判断。
总结来说，后缀数组是对字符串所有后缀按字典序排序后得到的结果，通常存储的是排序后后缀的起始位置。它就像一个“导航图”，帮助我们快速解决各种复杂的字符串问题，比如查找子串、重复子串、最长公共前缀等，是字符串处理领域中非常实用的工具。