LCP 陣列（最長共同前綴陣列）

後綴陣列把所有後綴按排序列出，但它完全不告訴你相鄰的後綴有多相似。LCP 陣列填補了這個缺口。對排序中每一對相鄰的後綴，它記錄它們開頭共享多少個字元——它們的最長共同前綴。這個搭檔陣列正是解鎖後綴陣列全部威力的關鍵，讓它在每項功能上都能匹敵後綴樹。

形式上，給定字串 S 及其後綴陣列 SA，LCP 陣列存 LCP[i] = 「SA[i] 處的後綴」與「SA[i-1] 處的後綴」（排序中緊鄰前一個）的最長共同前綴長度。對 "banana"，SA = [5,3,1,0,4,2] 給出排序後綴 a、ana、anana、banana、na、nana，其 LCP 陣列為 [-, 1, 3, 0, 0, 2]："ana" 與 "anana" 共享 "ana"（3），"na" 與 "nana" 共享 "na"（2），依此類推。有個漂亮的做法：Kasai 演算法用後綴陣列及其反陣列在 O(n) 時間建出 LCP 陣列，做法是依原字串順序掃描後綴，並觀察到當你移到「下一個更短的後綴」時 LCP 值至多下降一，所以總工作是線性的。再對 LCP 陣列做區間最小值查詢，就能得到任意兩個後綴（不只相鄰者）的最長共同前綴。

為何重要：LCP 陣列是從扁平後綴陣列通往後綴樹級查詢的橋樑。某區間內最小的 LCP 值，等於後綴樹中對應內部節點的字串深度，所以最大的 LCP 值就是最長重複子字串的長度；把 n - SA[i] - LCP[i] 加總可計算相異子字串數；而 LCP 資訊把模式搜尋從 O(m log n) 銳化到 O(m + log n)。簡言之，後綴陣列加 LCP 陣列是後綴樹在實務上、記憶體輕量的替代品——而 LCP 陣列正是提供「這些後綴重疊多少」這份純排序清單所欠缺知識的那部分。