POJ 3080 Blue Jeans DNA最長公共子串 KMP+暴力/後綴自動機

問題描述

給定 m（2 ≤ m ≤ 10）條長度 60 的 DNA 序列（字符集 {A,T,G,C}），求最長公共子串。長度 < 3 輸出 "no significant commonalities"，多解輸出字典序最小。

解法一：暴力枚舉 + KMP/strstr O(m·L³)

以第一條序列為基準，枚舉所有子串（O(L²)），對其餘 m-1 條用 KMP 或 strstr 匹配（O(mL)）。
L=60 很小，L³=216,000，乘 m=10 才 200 萬操作，極快。
按長度從大到小、起始位置從小到大枚舉，第一個匹配成功的即為答案。

代碼（strstr 版）

char dna[11][66];
int main() {
    int T, m; scanf("%d", &T);
    while (T--) {
        scanf("%d", &m);
        for (int i = 0; i < m; ++i) scanf("%s", dna[i]);
        
        int best_len = 0; char best[66];
        for (int i = 0; i < 60; ++i)
            for (int j = i+2; j < 60; ++j) { // 長度≥3
                int len = j - i + 1;
                if (len < best_len) continue;
                char sub[66]; strncpy(sub, dna[0]+i, len); sub[len]=0;
                
                bool ok = true;
                for (int k = 1; k < m; ++k)
                    if (!strstr(dna[k], sub)) { ok = false; break; }
                
                if (ok && (len > best_len || strcmp(sub, best) < 0)) {
                    best_len = len; strcpy(best, sub);
                }
            }
        if (best_len < 3) puts("no significant commonalities");
        else puts(best);
    }
}

解法二：KMP 優化匹配

預處理每個候選子串的 next 數組，在目標串中 KMP 匹配。雖然理論更快，但 L 很小，庫函數 strstr 通常已足夠（甚至更快）。

解法三：廣義後綴自動機/後綴數組 O(mL)

構建所有序列的廣義後綴自動機，統計每個狀態出現的序列數，找長度最大且出現於所有序列的狀態。屬於大殺器，本題數據小無需使用。

關鍵點

• 子串長度 ≥ 3 才有意義
• 字典序最小：同長度時 strcmp 比較
• 枚舉順序：長度降序、起始位置升序可優化剪枝