後綴數組求 LCS 完整代碼講解：從構建到查詢的 C++ 實現

貼出的代碼是典型的後綴數組 + LCP（最長公共前綴）數組求兩字符串最長公共子串（LCS）的實現。逐行拆解核心邏輯：

關鍵數據結構

• char *suff[100]：後綴指針數組，每個元素指向原串某個位置
• pstrcmp：qsort 比較函數，按字典序比較兩個後綴
• comlen_suff：計算兩後綴最長公共前綴長度，遇到 # 分隔符提前結束

算法流程

1. 拼接：arr = X + '#' + Y，# 保證不跨串匹配
2. 初始化後綴：suff[i] = &arr[i]，共 xlen + ylen + 1 個後綴
3. 排序：qsort(suff, len, sizeof(char*), pstrcmp)，按字典序排序
4. 掃描相鄰後綴：只需比較排序後相鄰的兩個後綴（來自不同原串），其 LCP 即為候選 LCS
5. 取最大：記錄最大 maxlen 及位置 suf_index
6. 輸出：outputLCS(suff[suf_index]) 打印前 maxlen 個字符

時間複雜度分析

• 構建後綴：O(n)
• 排序：O(n log n) × 比較耗時 O(n) → O(n² log n)（朴素 qsort 比較函數每次比較可能掃描整個後綴）
• 掃描 LCP：O(n²)
• 總體：O(n² log n)，n = 兩串總長

優化方向

1. DC3 / SA-IS 算法：O(n) 構建後綴數組
2. Kasai 算法：O(n) 計算 Height 數組（利用 Height[i] ≥ Height[i-1] - 1）
3. 雙關鍵字排序 + 倍增：O(n log n) 工程常用

後綴數組核心概念補充

• 子串：連續字符序列 S[i..j]
• 後綴：Suffix(i) = S[i..n-1]
• 字典序：逐字符比較，短前綴優先
• 後綴數組 SA：SA[k] 為第 k 小後綴的起始位置，滿足 Suffix(SA[i]) < Suffix(SA[i+1])
• Height 數組：Height[i] = LCP(Suffix(SA[i]), Suffix(SA[i-1]))

工程建議

除非學習算法原理，**生產環境直接用** ：

• C++：libdivsufsort、suffix_array (Boost)
• Python：pysuffixarray、suffix_trees
• Java：SuffixArray (Apache Commons Text)

手寫 DC3/SA-IS 只為面試/競賽，項目中維護成本太高。