SPOJ 220 RPLN - 後綴數組求多字串公共非重疊子串

題目大意

給定 m 個字串，求在所有字串中都出現至少兩次且兩次出現不重疊的子串的最大長度。

解法：後綴數組 + 二分答案 + 滑動窗口檢查

核心思路

1. 將所有字串用唯一分隔符拼接，構建後綴數組 SA 與 height
2. 二分答案長度 L
3. 檢查 check(L)：是否存在長度 ≥ L 的子串，在每個字串中至少出現兩次且不重疊

檢查函數 check(L)

掃描 height[]，將連續 height ≥ L 的後綴分為一組。
對每組，統計各字串中該子串出現的最小起始位置 down[i] 和最大起始位置 up[i]。
若對所有字串 i，up[i] - down[i] ≥ L，則該字串中存在兩個不重疊出現。
若所有字串均滿足 → 返回 true。

關鍵程式碼

const int MAXN = 110005;
int sa[MAXN], ht[MAXN], rk[MAXN];
int belong[MAXN]; // 每個後綴屬於哪個原字串
int up[11], down[11];

bool ok(int L, int m) {
    for (int i = 1; i <= m; i++)
        if (up[i] - down[i] < L) return false;
    return true;
}

bool check(int L, int m) {
    memset(up, -1, sizeof up);
    memset(down, -1, sizeof down);
    
    for (int i = 1; i < n; i++) {
        if (ht[i] < L) {
            if (ok(L, m)) return true;
            memset(up, -1, sizeof up);
            memset(down, -1, sizeof down);
            int id = belong[sa[i]];
            up[id] = down[id] = sa[i];
        } else {
            int id = belong[sa[i]];
            if (up[id] != -1) {
                up[id] = max(up[id], sa[i]);
                down[id] = min(down[id], sa[i]);
            } else up[id] = down[id] = sa[i];
        }
    }
    return ok(L, m);
}

複雜度

• 構建 SA：O(N log N), N = Σ|s_i|
• 二分 log(10000) 次，每次 O(N) 掃描
• 總計 O(N log N)

關鍵細節

• 分隔符必須唯一且不在字串中出現（用 'A'+i）
• height 區段劃分：height[i] < L 時重置統計
• 不重疊條件：max_pos - min_pos ≥ L 確保兩出現位置間距 ≥ 長度