POJ 3693 Maximum Repetition Substring：後綴數組+RMQ求最長重複子串

問題定義

給定字符串，求出現次數最多的「循環子串」（即形如 U^k 的子串，k 最大），若有多個輸出字典序最小者。

核心觀察

若子串 T 由長度為 l 的模式 U 重複 k 次構成，則在後綴數組中，SA[i] 和 SA[i]+l 的 LCP ≥ (k-1)*l。枚舉所有可能的 l (1~n-1)，以步長 l 掃描，利用 RMQ 快速查詢 LCP，即可計算最大重複次數。

算法流程

1. 構建後綴數組 SA、Rank、Height 數組（倍增法 O(n log n)）。
2. 預處理 Height 的 RMQ（ST 表 O(n log n)），支持 O(1) 區間最小值查詢（即 LCP）。
3. 枚舉長度 l = 1..n-1：
   • 對每個 i = 0, l, 2l, ...，查詢 LCP(i, i+l)。
   • 基本重複次數 k = LCP/l + 1。
   • 向左延伸：檢查 i - (l - LCP%l) 處是否能多一次重複，若能 k++。
   • 記錄全局最大 ans 及對應的所有 l。
4. 二次掃描 SA，找到字典序最小的滿足 ans 的子串輸出。

關鍵代碼片段

// RMQ 查詢 LCP
int rmq_query(int x, int y) {
    if (x == y) return d[x][0];
    if (x > y) swap(x, y);
    ++x;
    int k = 0; while ((1<<(k+1)) <= y-x+1) ++k;
    return min(d[x][k], d[y-(1<= 0 && lcp % l && rmq_query(rank[p], rank[p+l]) >= lcp) ++k;
            if (k > ans) { ans = k; vec.clear(); }
            if (k == ans) vec.push_back(l);
        }
    }
    // 找字典序最小
    for (int i = 0; i < n; ++i) {
        for (int l : vec) {
            if (SA[i] + l >= n) continue;
            if (rmq_query(i, rank[SA[i]+l]) >= (ans-1)*l) {
                // 輸出 SA[i] 起始長度 ans*l 的子串
                return;
            }
        }
    }
}

複雜度分析

• 後綴數組構建：O(n log n)
• RMQ 預處理：O(n log n)
• 枚舉 l：∑_l=1ⁿ n/l = O(n log n) 次 RMQ 查詢，每次 O(1)
• 總時間 O(n log n)，空間 O(n log n)

常見坑點

1. 字符串結尾需添加兩個哨兵（如 27 和 0），保證後綴數組正確。
2. 向左延伸判斷條件 p >= 0 && lcp % l && rmq_query(rank[p], rank[p+l]) >= lcp 嚴格防止越界與重複計數。
3. 輸出時需將整數編碼還原為字符（s[pos+i] + 'a' - 1）。

本題展示了後綴數組+RMQ 解決「最大重複子串」的標準套路，結合「枚舉長度+步長掃描+向左延伸」技巧，是字符串算法進階的經典練習。