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

POJ 3080 Blue Jeans：DNA 序列最長公共子串暴力解法

編輯：C++ 入門

題目大意

給定 m (2≤m≤10) 條 DNA 序列（長度固定 60，字符集 {A,T,G,C}），找出**最長**在所有序列中都出現的子串。若長度 < 3 輸出 no significant commonalities。多解輸出字典序最小者。多組測資。

暴力枚舉策略（通過）

參考序列取第一條。枚舉其所有子串（起點 i，長度 len），從長到短、同長度字典序從小到大檢查是否在其餘 m-1 條序列中均出現（strstr）。首個滿足即為答案。

複雜度：O(60² * m * 60) ≈ 1.3×10⁶，極快。

完整 AC 代碼（C++）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int m; cin >> m;
        vector s(m);
        for (int i=0;i> s[i];
        string ans = "";
        int maxLen = 0;
        // 枚舉第一條序列的所有子串
        for (int i=0;i<60;++i) {
            for (int len=3; len<=60-i; ++len) { // 至少長度 3
                string sub = s[0].substr(i, len);
                bool ok = true;
                for (int j=1;j maxLen || (len == maxLen && sub < ans)) {
                        maxLen = len;
                        ans = sub;
                    }
                }
            }
        }
        if (maxLen == 0) cout << "no significant commonalities\n";
        else cout << ans << '\n';
    }
    return 0;
}