我知道后缀数组本身的定义是它是一个字符串的所有后缀的排序数组。但是我试着去理解这个排序操作的意义是什么?假设我们创建一个字符串的所有后缀的数组，并选择不排序，继续构建LCP数组，在这种情况下，我们失去了什么，当我们试图解决这些常见的问题，如最长回文子字符串，最长重复子字符串?
您希望在后缀数组中对所有后缀进行排序的主要原因有两个:
首先，如果S和T是字符串，我们知道以下内容:
T是S的子字符串当且仅当它是S的后缀的前缀
例如，如果S是"avoidance"，T是"ida"，那么T是S的子字符串，因为它是后缀"idance"的前缀。因此，需要快速查询S的子字符串的应用程序可以根据搜索S的前缀或后缀来重新表述。
鉴于此，如果您有兴趣搜索S的后缀的前缀，那么将这些后缀存储在允许快速搜索的数据结构中是有意义的。如果我们把后缀放在一个数组中，那么保持它们的排序就可以让您查找各种前缀必须有效地放在哪里。因此，如果后缀数组是按顺序存储的S的所有后缀的数组，则可以快速搜索后缀的前缀，从而搜索S的子字符串。
关于你的第二个关于LCP数组的问题-如果后缀没有排序，你能计算它们吗?如果你这样做了，你会失去什么?-你完全可以计算任何数组，甚至是一个没有排序的后缀数组，所以没有根本的理由为什么你不能这样做。但是，排序后缀数组的LCP数组有一些很好的属性，而未排序后缀数组的LCP数组没有这些属性。例如，后缀数组中的LCP数组可用于确定相应后缀树中内部节点的深度，或计算最长公共扩展等。
排序后缀数组和LCP的一个非常重要的特性是，如果您计算所有字符串的成对LCP信息，则可以通过对LCP数组执行范围最小查询来计算任意字符串对的LCP。这样做的原因是，如果对后缀进行排序，则保留相邻字符串之间的最大重叠量。这在数组未排序的情况下不起作用(我将在最后再次提到这一点)
为了明确问题出在哪里，让我们以最长重复子串问题为例。使用后缀数组的正常线性时间算法如下:
- 为字符串t构造后缀数组
- 为广义后缀数组构造LCP数组
- 遍历后缀数组，找到LCP值最大的字符串。
重要的是要考虑为什么最后一步是有效的。考虑任何重复两次的子字符串，称其为s。因为任何子字符串都是后缀的前缀，这意味着字符串Sα和sβ;必须是字符串t的后缀。如果按排序顺序存储后缀数组，那么所有以前缀S开头的字符串将连续出现在后缀数组中(您知道为什么吗?)因此，如果S是最长的重复子串，那么第一个以S开头的后缀有一个LCP，其下一个字符串的长度为|S|
现在，考虑如果您执行而不对数组进行排序会发生什么。在这种情况下，如果S是最长的重复子串，则字符串Sα和sβ;仍然是字符串t的后缀，但是，它们在后缀数组中不一定是连续的，因此不一定有一个线性时间算法来找到它们。例如，考虑字符串abracadabra
未排序后缀数组
abracadabra$
bracadabra$
racadabra$
acadabra$
cadabra$
adabra$
dabra$
abra$
bra$
ra$
a$
$
用LCP信息注释后，得到
0 abracadabra$
0 bracadabra$
0 racadabra$
0 acadabra$
0 cadabra$
0 adabra$
0 dabra$
0 abra$
0 bra$
0 ra$
0 a$
$
所以你可以看到这个算法不会找到"abra"，因为它们不是连续的。你仍然可以通过尝试所有对来确定它是"abra"，但这对于大字符串来说并不有效。
我前面提到过，排序后缀数组中相邻字符串对的LCP信息可以用来计算排序后缀数组中任意字符串对的LCP信息。如果字符串未排序，则不成立;上面，你可以看到所有的字符串都有相邻的成对LCP为0，尽管有些字符串确实有非零的公共前缀。
希望这对你有帮助!