UVA 1223：後綴數組求最長重複子串長度

題目大意

給定字串 S（長度 ≤ 5000），求最長子串長度，使其在 S 中至少出現兩次（允許重疊）。

解法

構建後綴數組與高度數組，答案即為 Height 數組中的最大值。因為 Height[i] 表示 SA[i] 和 SA[i-1] 的最長公共前綴，若最大值為 L，則存在長度為 L 的子串出現至少兩次。

代碼片段 (C++)

// 倍增法構建 SA，計算 Height
// 遍歷 Height 取最大值即為答案
// 複雜度 O(n log n)，n=5000 極快