POJ 3080 Blue Jeans：最長公共子串 KMP + 暴力枚舉

題目大意

• `m (2≤10)` 條 DNA 序列（長度 60，字符集 `ATGC`）。
• 求所有序列的最長公共子串（長度 ≥3），若多解輸出字典序最小；無解輸出 `no significant commonalities`。

暴力枚舉 + 字符串查找

以第一條序列為基準，枚舉所有子串（長度 3..60），按長度降序、字典序升序檢查是否在其餘所有序列中出現（`strstr` / `string::find`）。
找到第一個即為答案。
複雜度：`O(L² * m * L)` = `60² * 10 * 60 ≈ 2e6`，極快。

KMP 優化版

對每個候選子串構建 KMP `next` 數組，在其餘序列中 KMP 匹配，同樣可行。

完整代碼（暴力版）

#include 
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int m; cin >> m;
        vector dna(m);
        for (int i = 0; i < m; ++i) cin >> dna[i];
        string ans = "";
        int L = dna[0].size();
        for (int len = L; len >= 3; --len) {
            string best = "";
            for (int i = 0; i + len <= L; ++i) {
                string sub = dna[0].substr(i, len);
                bool ok = true;
                for (int j = 1; j < m; ++j)
                    if (dna[j].find(sub) == string::npos) { ok = false; break; }
                if (ok) {
                    if (best.empty() || sub < best) best = sub;
                }
            }
            if (!best.empty()) { ans = best; break; }
        }
        if (ans.empty()) cout << "no significant commonalities\n";
        else cout << ans << "\n";
    }
    return 0;
}

複雜度

• 暴力：`O(L² * m * L)`，`L=60` 瞬間通過。
• KMP：`O(L² * m * L)` 但常數較大，無必要。