牛奶模式問題：最長重複子序列（K 次）求解

問題描述

給定 N 天奶質數據（0~1,000,000），找出至少重複 K 次（可重疊）的最長子序列長度。N ≤ 20,000，K ≥ 2。

解法思路

經典後綴數組 + 二分查找或後綴自動機 (SAM)問題：

1. 構建後綴數組，計算高度數組 (LCP)。
2. 二分答案長度 L，檢查是否存在至少 K 個後綴的 LCP ≥ L。
3. 檢查時利用高度數組分組，統計連續段中高度 ≥ L 的後綴數量是否 ≥ K。

複雜度

• 後綴數組構建 O(N log N) 或 O(N)。
• 二分查找 O(log N) * O(N) 檢查，總體 O(N log N)。

參考實現

詳細代碼與解析

關鍵點

重疊允許意味著只需關注後綴數組中相鄰高度，無需額外去重。二分答案轉化為判定問題，配合高度數組線性掃描判定。

此題是後綴數組應用的典型範例，掌握模板可解決大多數最長重複子串變體。