問題描述
給定字符串，求重複次數最多的子串（次數相同取字典序最小）。重複定義：子串出現 k 次（可重疊），最大化 k。
核心算法：枚舉長度 + LCP
- 構建後綴數組
sa、rank、height
- RMQ 預處理
height 答 LCP 查詢
- 枚舉長度 l，按 l 分塊：
i, i+l, i+2l...
- 對每對相鄰塊查 LCP，得匹配長度
tmp
- 出現次數
ti = tmp/l + 1；若 tmp%l > 0 向前延伸 l - tmp%l 再查 LCP，可能 +1
- 記錄最大
ti 及對應長度
字典序最小輸出
利用 sa 本身有序性：按 sa 順序掃描，首個滿足 lcp(sa[i], sa[i]+len) ≥ (Max-1)*len 的即為答案。
關鍵代碼片段
for (int l=1; l=0 && tmp%l && lcp(v, v+l) >= tmp) ti++;
// 更新 Max, ans[]
}
}
for (int i=1; i<=n; i++)
for (int len : ans)
if (lcp(sa[i], sa[i]+len) >= (Max-1)*len) { output from sa[i]; break; }
時間復雜度 O(n log n)（枚舉長度調和級數），空間 O(n log n)（RMQ）。
