後綴數組：後綴數組是什麼？解決字符串問題的利器

後綴數組是對字符串所有後綴按字典序排序後，存儲排序後綴起始位置的數組。後綴指從字符串每個位置開始到末尾的子串（如“banana”的後綴有“banana”“anana”等）。字典序比較規則爲：首字符不同則按字符大小比較，相同則依次比較後續字符，若一後綴是另一前綴則較短的更小。 以“abrac”爲例，其後綴排序後起始位置數組爲[0,3,4,1,2]（如位置0的“abrac”<位置3的“ac”，再依次排列）。 後綴數組的核心價值在於高效解決字符串問題：通過排序後相鄰後綴的緊密關係（公共前綴長），可快速處理最長重複子串、子串存在性等。例如，用LCP數組找最長重複子串，或通過二分查找驗證子串是否存在。 總結：後綴數組通過排序後綴起始位置，爲字符串問題提供高效解決方案，是字符串處理的實用工具。