POJ 1743 Musical Themes - 後綴數組 + 二分答案檢查重複主題

題目轉化

長度 N ≤ 5000 的音高序列 (1~88)。求最長子序列滿足：
1. 長度 ≥ 5
2. 出現至少兩次 (允許整體平移/轉調，即差值序列相同)
3. 兩次出現不重疊

對相鄰音高做差分 d[i] = a[i+1]-a[i] + 100 (偏移避免負數)，問題轉為：差分陣列中最長重複且不重疊子串長度 + 1。

後綴數組 + 二分

1. 建構差分陣列 s[] 長度 n-1，構建後綴數組 SA、Height。
2. 二分長度 L (1~n)。檢查是否存在 Height ≥ L 的連續區段，且區段內 SA 最大值 - 最小值 ≥ L (不重疊)。
3. 若存在 → 答案 ≥ L+1 (含首音)。

關鍵檢查函數

bool check(int L) {
    int mn = n, mx = -1;
    for (int i = 1; i < n; ++i) {
        if (height[i] >= L) {
            mn = min(mn, sa[i]); mx = max(mx, sa[i]);
            mn = min(mn, sa[i-1]); mx = max(mx, sa[i-1]);
        } else {
            if (mx - mn >= L) return true;
            mn = n; mx = -1;
        }
    }
    return mx - mn >= L;
}

完整代碼 (DC3/SA-IS 均可，這裡用倍增 O(n log n))

#include 
using namespace std;
const int MAXN = 20005;
int s[MAXN], sa[MAXN], rk[MAXN], ht[MAXN], tmp[MAXN], cnt[MAXN];

void buildSA(int n, int m) { // m=字元範圍
    for(int i=0;i=0;--i) sa[--cnt[s[i]]]=i;
    for(int k=1; k=k) tmp[p++]=sa[i]-k;
        fill(cnt, cnt+m, 0);
        for(int i=0;i=0;--i) sa[--cnt[rk[tmp[i]]]]=tmp[i];
        copy(rk, rk+n, tmp);
        p=1; rk[sa[0]]=0;
        for(int i=1;i=n) break;
        m=p;
    }
    // Height
    for(int i=0,k=0;i> n;
    for(int i=0;i> s[i];
    for(int i=0;i=4? ans+1 : 0) << "\n"; // 長度≥5 → 差分長度≥4
    return 0;
}

複雜度

• 建 SA：O(n log n)，n=5000 極快。
• 二分 + 掃描：O(n log n)。
• 總時間 < 10ms，空間 < 1MB。

替代方案：Hash + 二分

對長度 L 子串雙重哈希 (或單哈希 + 驗證)，用 `unordered_map>` 記錄位置，檢查是否有不重疊位置。期望 O(n log n)，碼量較短，工程上常用。

後綴數組是「最長重複子串/子序列」問題的標準重武器，掌握 SA + Height + 二分檢查模板，同類問題 (最長公共子串、最長重複非重疊子串) 皆可套用。