Codeforces 244D Match & Catch：字串哈希與後綴數組雙解法

問題描述

給定兩個字串，找出最小長度 L，使得存在長度為 L 的子串在兩字串中各自恰好出現一次，且這兩個子串相同。若不存在輸出 -1。

解法一：字串哈希 (O(n²))

BKDR Hash 函數

unsigned int BKDRHash(char *str) {
    unsigned int seed = 131, hash = 0;
    while (*str) hash = hash * seed + (*str++);
    return hash & 0x7FFFFFFF;
}

雙重哈希避免衝突

• 使用 unsigned long long 自然溢位作為哈希值
• 自定義哈希表處理衝突（鏈地址法）
• 記錄每個子串在兩字串中的出現次數

核心邏輯

1. 枚舉長度 len = 1..min(n,m)
2. 對每個長度，計算兩字串所有子串哈希值
3. 檢查是否存在哈希值在兩字串中均恰好出現 1 次
4. 最先滿足條件的長度即為答案

關鍵代碼片段

ULL P[maxn], h1[maxn], h2[maxn];
void hash_pre() { P[0]=1; for(i=1;i

解法二：後綴數組 (O(n log n))
核心思想
將兩字串連接：S = s1 + '#' + s2 + '$' (用不在字母表中的分隔符)。構建後綴數組 SA 與 Height 陣列。

判斷條件
對於 Height[i] (即 SA[i] 與 SA[i-1] 的 LCP)：

兩後綴分屬不同原字串 (一個在 s1，一個在 s2)
Height[i] > max(Height[i-1], Height[i+1]) — 確保該長度在兩字串中唯一
答案為所有滿足條件的 max(Height[i-1], Height[i+1]) + 1 的最小值


關鍵代碼
void solve(int n) {
    int ans = INF;
    for (int i = 1; i <= n; ++i) {
        if (!height[i]) continue;
        if ((sa[i] < l && sa[i-1] < l) || (sa[i] >= l && sa[i-1] >= l)) continue; // 同字串
        int pre = height[i-1] + 1;
        int nxt = height[i+1] + 1;
        if (height[i] >= max(pre, nxt)) ans = min(ans, max(pre, nxt));
    }
    if (ans == INF) puts("-1"); else printf("%d\n", ans);
}

兩種解法對比

維度
字串哈希
後綴數組
時間複雜度
O(n²)
O(n log n)
實作難度
中等
高 (需正確構建 SA/Height)
衝突風險
極低 (雙重哈希)
無
適用場景
n ≤ 5000, 競賽速解
n ≤ 10⁵, 要求嚴格正確


總結
本題展示了字串問題的兩大核心工具：哈希適合快速原型與中等規模；後綴數組提供理論最優與確定性保證。實戰中可根據數據範圍與時間限制靈活選擇。