後綴數組是什麼？我們先從“後綴”說起。對於一個字符串，比如“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）可以幫助我們找到原字符串中最長的重複子串。或者，如果我們想知道某個子串是否存在，只需要在排序後的後綴數組中，通過二分查找對應的起始位置，就能快速判斷。
總結來說，後綴數組是對字符串所有後綴按字典序排序後得到的結果，通常存儲的是排序後後綴的起始位置。它就像一個“導航圖”，幫助我們快速解決各種複雜的字符串問題，比如查找子串、重複子串、最長公共前綴等，是字符串處理領域中非常實用的工具。