您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

POJ 1743 Musical Theme：後綴數組 + 二分查找最長非重疊重複子串（含轉調）

編輯：C++ 入門

問題轉化

給定長度 N (≤20000) 的音符序列（1..88）。尋找最長「主題」：長度 ≥5，在序列中至少出現兩次（允許整體平移 transposition，即所有音符加同一常數），且兩次出現不重疊。

關鍵觀察：平移不變性 ⇒ 只需考慮 相鄰差分序列。設原序列 s[0..N-1]，構造差分 d[i] = s[i+1] - s[i] + 90（+90 使值為正），長度 N-1。問題轉化為：在差分序列中找最長的 不重疊重複子串，長度 ≥4（對應原主題 ≥5）。

後綴數組 + 二分 + Height 分組

構建差分序列的後綴數組 SA 和 Height 數組（O(N log N) 倍增算法）。
二分答案長度 L（4 到 N/2）。
判定函數 check(L)：
　　遍歷 SA，將 Height[i] ≥ L 的相鄰後綴分為同一組。
　　每組內記錄最小/最大起始位置 MinPos, MaxPos。
　　若 MaxPos - MinPos > L，說明存在兩個不重疊的長度 L 子串 → 返回 true。

核心 C++ 代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 20010;
int sa[MAXN], rk[MAXN], ht[MAXN], tp[MAXN], c[MAXN];
int s[MAXN], n;

void build_sa(int m) { // m = 值域上界
    int *x = rk, *y = tp;
    for (int i = 0; i < m; i++) c[i] = 0;
    for (int i = 0; i < n; i++) c[x[i]=s[i]]++;
    for (int i = 1; i < m; i++) c[i] += c[i-1];
    for (int i = n-1; i >= 0; i--) sa[--c[x[i]]] = i;
    for (int k = 1; k <= n; k <<= 1) {
        int p = 0;
        for (int i = n-k; i < n; i++) y[p++] = i;
        for (int i = 0; i < n; i++) if (sa[i] >= k) y[p++] = sa[i] - k;
        fill(c, c+m, 0);
        for (int i = 0; i < n; i++) c[x[y[i]]]++;
        for (int i = 1; i < m; i++) c[i] += c[i-1];
        for (int i = n-1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];
        swap(x, y); p = 1; x[sa[0]] = 0;
        for (int i = 1; i < n; i++)
            x[sa[i]] = (y[sa[i-1]]==y[sa[i]] && y[sa[i-1]+k]==y[sa[i]+k]) ? p-1 : p++;
        if (p >= n) break; m = p;
    }
}

void get_height() {
    for (int i = 0; i < n; i++) rk[sa[i]] = i;
    int k = 0;
    for (int i = 0; i < n; i++) {
        if (k) k--;
        int j = sa[rk[i]-1];
        while (i+k < n && j+k < n && s[i+k]==s[j+k]) k++;
        ht[rk[i]] = k;
    }
}

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

int main() {
    while (scanf("%d", &n) && n) {
        for (int i = 0; i < n; i++) scanf("%d", &s[i]);
        for (int i = n-1; i > 0; i--) s[i] = s[i] - s[i-1] + 90;
        n--; // 差分長度
        for (int i = 0; i < n; i++) s[i] = s[i+1];
        s[n] = 0; // 哨兵
        build_sa(200); get_height();
        int lo = 1, hi = n/2, ans = 0;
        while (lo <= hi) {
            int mid = (lo+hi)/2;
            if (check(mid)) { ans = mid; lo = mid+1; }
            else hi = mid-1;
        }
        if (ans < 4) puts("0");
        else printf("%d\n", ans+1); // +1 還原原主題長度
    }
    return 0;
}