POJ 3294 / UVA 11107 Life Forms：後綴數組 + 二分答案求多數字符串公共子串

POJ 3294 / UVA 11107 Life Forms：後綴數組 + 二分答案求多數字符串公共子串

給定 n (≤100) 個 DNA 字符串（長度 ≤ 1000），求**最長子串**使其在**超過一半**字符串中出現。若多解，按字典序全部輸出；無解輸出 ?。

核心思路：廣義後綴數組 + Height 數組掃描 + 二分長度

1. 拼接：用互不相同的分隔符（'z'+1, 'z'+2, …）將所有字符串拼成一個大串 S。
2. 構建後綴數組 SA 和 Height 數組：SA[i] = 第 i 小後綴起始位置，Height[i] = SA[i] 與 SA[i-1] 的 LCP 長度。
3. 預處理 belong[pos]：記錄 S 中每個位置屬於第幾個原字符串（分隔符屬於 0）。
4. 二分答案 L：檢查是否存在長度 ≥ L 的子串在 > n/2 個字符串中出現。
   掃描 Height，維護連續段中 Height ≥ L 的後綴集合，統計不同 belong 數量。若 > n/2 返回 true。
5. 輸出所有解：以最大 L 再次掃描，收集所有滿足條件的子串（SA 順序保證字典序）。

關鍵代碼片段

// 後綴數組構建（倍增算法 O(n log n)）
void build_sa(vector<int>& s, int m) { ... }
void get_height(vector<int>& s) { ... }

// 檢查長度 L 是否可行
bool check(int L, int n_str) {
    unordered_set<int> seen;
    for (int i = 1; i <= N; ++i) {
        if (height[i] >= L) seen.insert(belong[sa[i]]);
        else { if (seen.size() > n_str/2) return true; seen.clear(); }
    }
    return seen.size() > n_str/2;
}

// 收集所有長度 L 的解（字典序）
vector<string> collect(int L, int n_str) {
    vector<string> ans;
    unordered_set<int> seen;
    int start = 1;
    for (int i = 1; i <= N; ++i) {
        if (height[i] >= L) {
            seen.insert(belong[sa[i]]);
        } else {
            if (seen.size() > n_str/2) {
                string sub = S.substr(sa[i-1], L);
                ans.push_back(sub);
            }
            seen.clear();
        }
    }
    if (seen.size() > n_str/2) ans.push_back(S.substr(sa[N], L));
    sort(ans.begin(), ans.end());
    ans.erase(unique(ans.begin(), ans.end()), ans.end());
    return ans;
}

完整流程

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, first = 1;
    while (cin >> n, n) {
        if (!first) cout << '\n'; first = 0;
        string S; vector<int> s; vector<int> belong;
        for (int i = 1; i <= n; ++i) {
            string t; cin >> t;
            for (char c : t) { S += c; s.push_back(c - 'a' + 1); belong.push_back(i); }
            S += char('z' + i); s.push_back(27 + i); belong.push_back(0);  // 唯一分隔符
        }
        S += '$'; s.push_back(0);
        int N = s.size() - 1;
        build_sa(s, 30 + n);
        get_height(s);
        int L = 0, lo = 1, hi = 1000;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (check(mid, n)) { L = mid; lo = mid + 1; }
            else hi = mid - 1;
        }
        if (L == 0) { cout << "?\n"; continue; }
        auto ans = collect(L, n);
        for (auto& x : ans) cout << x << '\n';
    }
    return 0;
}

複雜度

• 構建 SA：O(N log N)，N ≤ 100×1000 + 100 ≈ 10⁵。
• 二分 + 掃描：O(log 1000 × N) ≈ 10⁶。
• 總體：O(N log N)，POJ 時限 5s 輕鬆通過。

關鍵避坑

1. 分隔符必須唯一且不在字母表中：用 'z'+i 確保不與 a-z 衝突，且互不相同。
2. Height 掃描邏輯：連續段 Height ≥ L 對應一組共享前綴 ≥ L 的後綴，統計其 belong 去重計數。
3. 字典序輸出：SA 本身按字典序排序，掃描順序即為字典序，收集去重即可。

總結

POJ 3294 是廣義後綴數組的經典應用：多字符串公共子串問題統一拼接、構建 SA、Height 掃描 + 二分答案。掌握倍增構建 SA、Height 含義、連續段統計不同字符串三大核心，即可解決所有「多串公共子串/子序列」問題。