POJ 3693 Maximum Repetition Substring：後綴陣列 + RMQ 完整解析

問題描述

給定一個僅含小寫字母的字串（長度 ≤ 100,000），找出其子字串中「重複次數」最大者。重複次數定義：字串可被分割為 R 個相同的連續子字串，最大的 R 即為重複次數。若有多解，輸出字典序最小者。

核心演算法：後綴陣列 + LCP + RMQ + 區間枚舉

關鍵觀察

若長度為 L 的子字串連續重複 R 次，則在位置 i, i+L, i+2L... 形成等差數列的後綴，其兩兩之間的最長公共前綴（LCP）至少為 (R-1)L。因此只需枚舉長度 L，檢查位置 i 和 i+L 的 LCP。

演算法流程

1. 建構後綴陣列 (SA)：O(n log n) 倍增法，得到 sa[]（排名→位置）、rank[]（位置→排名）、height[]（相鄰後綴 LCP）。
2. RMQ 預處理：對 height[] 建立稀疏表，O(1) 查詢任意區間最小值（即任意兩後綴 LCP）。
3. 枚舉長度 L (1 ~ n)：
   • 對每個 k，檢查位置 kL 和 (k+1)L 的 LCP = len。
   • 最大重複數 R = len / L + 1。
   • 向左擴展：若 len % L != 0，嘗試向左補齊 L - len%L 個字元，檢查是否能增加重複數（利用 LCP 查詢）。
4. 記錄最大 R 及對應的 L 集合。
5. 字典序最小：遍歷 SA 陣列，第一個滿足 LCP(sa[i], sa[i]+L) >= (R-1)*L 的位置即為答案起始點。

完整優化程式碼 (C++)

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int LOGN = 18; // log2(100000) < 17

int n;
char str[MAXN];
int sa[MAXN], rk[MAXN], ht[MAXN];
int tmp[MAXN], cnt[MAXN];
int st[MAXN][LOGN], lg2[MAXN];

// SA 倍增構建 (DC3/DC3 或標準倍增)
void build_sa(int m = 256) {
    int *x = tmp, *y = cnt; // 臨時陣列復用
    for (int i=0;i=0;--i) sa[--cnt[x[i]]]=i;

    for (int k=1, p=1; p=k) y[p++]=sa[i]-k;

        fill(cnt, cnt+m, 0);
        for (int i=0;i=0;--i) sa[--cnt[x[y[i]]]]=y[i];

        swap(x, y);
        p=1; x[sa[0]]=0;
        for (int i=1;i>1]+1;
    for (int i=0;ib) swap(a,b);
    ++a;
    int k=lg2[b-a+1];
    return min(st[a][k], st[b-(1<>str) {
        if (str[0]=='#') break;
        n=strlen(str);
        build_sa();
        build_rmq();

        int bestR=1, bestL=0;
        vector candL;

        for (int L=1; L<=n; ++L) {
            int maxR=1;
            for (int i=0; i+L=ext && get_lcp(i-ext, i-ext+L) >= lcp) ++R;
                }
                if (R > maxR) {
                    maxR = R;
                    candL.clear(); candL.push_back(L);
                } else if (R == maxR) {
                    candL.push_back(L);
                }
            }
            if (maxR > bestR) {
                bestR = maxR;
                bestL = L;
            }
        }

        // 找字典序最小
        int ansPos=-1, ansLen=0;
        for (int L : candL) {
            if (L != bestL) continue;
            for (int i=1;i n) continue;
                if (get_lcp(pos, pos+bestL) >= (bestR-1)*bestL) {
                    ansPos = pos; ansLen = bestR*bestL; break;
                }
            }
            if (ansPos!=-1) break;
        }

        cout << "Case " << cas++ << ": ";
        for (int i=0;i

複雜度與優化要點

時間：SA O(n log n) + RMQ O(n log n) + 枚舉 O(n log n)（調和級數 Σ n/L ≈ n log n）。總體 O(n log n)。
空間：O(n log n)（稀疏表）。
關鍵優化：向左擴展時只需檢查一次 L - len%L，證明見原題分析；字典序最小直接掃 SA 陣列。


總結
本題是後綴陣列與 RMQ 結合的經典應用，核心在於「枚舉長度 + LCP 查詢 + 向左擴展補齊」。掌握此模板可解決大多數「最大重複子字串」類問題。