MATLAB 尋找兩序列多個最長公共子串：後綴陣列法原理解析

問題定義

給定兩序列 A=[01111000110]、B=[10010100110]，需找出 A 中「最長前綴」且該前綴也出現於 B 中的所有子串（例：011、110、00110）。

演算法思路：廣義後綴陣列

1. 串接字串：將 A、B 以唯一分隔符（如 $、#）合併為 S = A + '$' + B + '#'。
2. 建構後綴陣列：對 S 所有後綴排序，得到 SA 陣列。
3. 計算 LCP 陣列：相鄰後綴的最長公共前綴長度。
4. 篩選跨序列配對：僅保留一個後綴屬於 A、另一個屬於 B 的相鄰配對。
5. 取最大 LCP：對應長度即為最長公共子串長度；若有多個相同長度，皆為解。

MATLAB 實作關鍵點

• MATLAB 無內建後綴陣列函數，需自行實作或呼叫 C/C++ MEX。
• 資料量小（長度 < 1000）時，暴力雙重迴圈 O(n²m) 亦可接受。
• 推薦使用 File Exchange 現成工具箱 加速開發。

複雜度分析

結語

「多個最長公共子串」問題本質屬於字串學經典議題，後綴陣列是理論最優解；MATLAB 環境下建議優先套用現成工具箱，或將核心演算法移植至 C/C++ MEX 以兼顧效能與開發效率。