POJ 3080 Blue Jeans：多字串最長公共子串暴力枚舉 + strstr 優化

題目轉化與資料範圍分析

POJ 3080《Blue Jeans》給定 m 條 DNA 序列（m ≤ 10，每條長度固定 60），尋找最長子串使其在所有序列中都出現。若最長長度 < 3 輸出 "no significant commonalities"，多解取字典序最小者。

關鍵觀察：m ≤ 10、長度固定 60 → 以第一條序列為母串，枚舉其所有子串（最多 60×61/2 = 1830 個），對每個子串檢查是否存在於其餘 m-1 條序列中。總操作約 1830 × 9 × 60 < 10⁶，暴力完全可行。

核心演算法流程

1. 讀入 m 條序列存入 DNA[1..m]
2. 對母串 DNA[1] 枚舉所有子串長度 len = 1..60，起始位置 i = 0..60-len
3. 提取子串 Copy = DNA[1].substr(i, len)
4. 檢查 strstr(DNA[k], Copy) != NULL 對所有 k = 2..m
5. 滿足條件時更新答案：長度更長 → 直接替換；長度相同 → strcmp 取字典序較小者

關鍵優化：C 庫函數 strstr

strstr(haystack, needle) 以高度優化的演算法（通常為 Two-Way 或 Boyer-Moore 變體）在 haystack 中尋找 needle，若找到返回指標否則返回 NULL。比手寫 KMP/BF 更快且程式碼極簡。

完整 AC 程式碼

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXM = 10, LEN = 60;
char DNA[MAXM+1][LEN+1];
char ans[LEN+1], tmp[LEN+1];

int main() {
    int T, m;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &m);
        for (int i = 1; i <= m; ++i) scanf("%s", DNA[i]);

        int bestLen = -1;
        ans[0] = '\0';

        for (int len = 1; len <= LEN; ++len) {
            for (int i = 0; i + len <= LEN; ++i) {
                strncpy(tmp, DNA[1] + i, len);
                tmp[len] = '\0';

                bool ok = true;
                for (int k = 2; k <= m; ++k)
                    if (!strstr(DNA[k], tmp)) { ok = false; break; }

                if (ok) {
                    if (len > bestLen) {
                        bestLen = len;
                        strcpy(ans, tmp);
                    } else if (len == bestLen && strcmp(tmp, ans) < 0) {
                        strcpy(ans, tmp);
                    }
                }
            }
        }

        if (bestLen < 3) puts("no significant commonalities");
        else puts(ans);
    }
    return 0;
}

複雜度與邊界情況

• 時間：O(T × m × L³) ≈ 100 × 10 × 60³ = 2.16×10⁷，實測 < 0.1s
• 空間：O(m × L) = 600 字元
• 字典序比較：strcmp 直接處理
• 長度 < 3 特判：題目要求輸出固定字串