POJ 3882 Stammering Aliens：後綴數組 / 字符串 Hash + 二分求最長重複子串

問題描述

給定長度 ≤ 40,000 的字符串，求出現次數 ≥ m 的最長子串長度及其最右出現位置。多測試用例，m=0 結束。

方法一：後綴數組 + Height 數組 + 單調隊列

1. 構建後綴數組 SA（倍增算法 O(n log n)）和 Height 數組（Kasai 算法 O(n)）。
2. Height[i] = LCP(SA[i], SA[i-1])。
3. 問題轉化：找長度 ≥ L 且在 Height 中連續 ≥ m-1 個值 ≥ L 的最大 L。即滑動窗口最小值最大化。
4. 二分長度 L，檢查是否存在長度 ≥ L 的窗口大小 ≥ m 的連續段。用單調隊列維護窗口最小值，O(n) 檢查。
5. 找到最大 L 後，再掃描一次找最右位置（SA 值最大）。

方法二：字符串 Hash + 二分（更簡潔）

1. 預計算前綴 Hash H[i] 和冪次 P[i]（模 2^64 自然溢出，或雙模）。
2. 子串 Hash get(l, r) = H[r] - H[l-1]*P[r-l+1]。
3. 二分長度 L：用 unordered_map 統計每個長度 L 子串的 Hash 出現次數及最右位置。若有次數 ≥ m，返回 true。
4. 二分結束得到最大 L，再掃描一次輸出最右位置。

Hash 版代碼框架

using ULL = unsigned long long;
const ULL BASE = 131;
ULL H[MAXN], P[MAXN];

void build_hash(const string& s) {
    int n = s.size();
    P[0] = 1;
    for (int i = 1; i <= n; ++i) {
        P[i] = P[i-1] * BASE;
        H[i] = H[i-1] * BASE + s[i-1];
    }
}
ULL get_hash(int l, int r) {  // 1-based, [l, r]
    return H[r] - H[l-1] * P[r-l+1];
}

bool check(int L, int m, int& pos) {
    unordered_map cnt, last_pos;
    int n = s.size();
    for (int i = 1; i + L - 1 <= n; ++i) {
        ULL h = get_hash(i, i+L-1);
        if (++cnt[h] >= m) {
            pos = max(pos, i + L - 1);  // 末尾位置
            return true;
        }
        last_pos[h] = i + L - 1;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m;
    string s;
    while (cin >> m, m) {
        cin >> s;
        build_hash(s);
        int l = 1, r = s.size(), ans_len = 0, ans_pos = 0;
        while (l <= r) {
            int mid = (l + r) >> 1;
            int pos = 0;
            if (check(mid, m, pos)) {
                ans_len = mid;
                ans_pos = pos;
                l = mid + 1;
            } else r = mid - 1;
        }
        if (ans_len == 0) cout << "none\n";
        else cout << ans_len << ' ' << ans_pos << '\n';
    }
    return 0;
}

複雜度

• 後綴數組：O(n log n) 構建，O(n log n) 二分檢查。
• Hash：O(n log n) 期望（unordered_map），常數更小，代碼更短。
• n=40000，兩種方法均可 AC。

關鍵點

1. Hash 碰撞風險極低（64 位自然溢出），競賽常用。
2. 二分答案 + 滑動窗口/Hash 統計是「最長重複子串 ≥ m 次」標準套路。
3. 輸出最右位置 = 子串結束位置最大值。