POJ 3080：Blue Jeans——最長公共子串二分 + Hash/RK

題目描述

m 條 DNA 序列（m ≤ 10，長 ≤ 60），找最長公共子串（至少長度 1）。輸出字典序最小者，無則輸出 "no significant commonalities"。

解法：二分長度 + 滾動哈希

1. 二分答案長度 L
2. 取第一條序列的所有長 L 子串計算哈希，存入集合
3. 對其餘序列，計算所有長 L 子串哈希，取交集
4. 交集非空 ⇒ 存在公共子串，驗證碰撞後記錄候選
5. 二分結束後，從候選中選字典序最小

關鍵優化

• 序列長 ≤ 60，暴力枚舉子串 O(L·60) 完全足夠，無需複雜哈希
• 直接用 str.substr(i,L) 比較，C++ set<string> 自動去重排序

C++ 簡化實現

#include <cstdio>
#include <set>
#include <string>
#include <algorithm>
using namespace std;
char s[11][65];
int main() {
    int T; scanf("%d",&T);
    while(T--) {
        int m; scanf("%d",&m);
        for(int i=0;i=1; --L) { // 從長到短枚舉
            set common;
            for(int i=0; i+L<=strlen(s[0]); ++i)
                common.insert(string(s[0]+i, L));
            for(int k=1; k cur;
                for(int i=0; i+L<=strlen(s[k]); ++i) {
                    string sub(s[k]+i, L);
                    if(common.count(sub)) cur.insert(sub);
                }
                common.swap(cur);
                if(common.empty()) break;
            }
            if(!common.empty()) { ans = *common.begin(); break; }
        }
        if(ans.empty()) puts("no significant commonalities");
        else printf("%s\n", ans.c_str());
    }
    return 0;
}

複雜度

• 枚舉長度 60..1，每長度 O(m × 60² log 60) ≈ 10 × 3600 × 6 ≈ 2×10⁵
• 總操作極少，0ms 級別