奶牛基因组学(Bovine Genomics G) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>
using namespace std;

using ull = unsigned long long;
const ull BASE = 13131;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<string> spot(n), plain(n);
    for (int i = 0; i < n; ++i) cin >> spot[i];
    for (int i = 0; i < n; ++i) cin >> plain[i];

    vector<ull> pw(m + 1, 1);
    for (int j = 1; j <= m; ++j) pw[j] = pw[j - 1] * BASE;

    vector<vector<ull>> hs(n, vector<ull>(m + 1, 0)), hp(n, vector<ull>(m + 1, 0));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            hs[i][j + 1] = hs[i][j] * BASE + (ull)spot[i][j];
            hp[i][j + 1] = hp[i][j] * BASE + (ull)plain[i][j];
        }
    }

    auto check = [&](int len) -> bool {
        unordered_set<ull> st;
        st.reserve(n * 2);
        for (int l = 0; l + len <= m; ++l) {
            st.clear();
            for (int i = 0; i < n; ++i) {
                ull v = hs[i][l + len] - hs[i][l] * pw[len];
                st.insert(v);
            }
            bool ok = true;
            for (int i = 0; i < n; ++i) {
                ull v = hp[i][l + len] - hp[i][l] * pw[len];
                if (st.find(v) != st.end()) {
                    ok = false;
                    break;
                }
            }
            if (ok) return true;
        }
        return false;
    };

    int lo = 1, hi = m, ans = m;
    while (lo <= hi) {
        int mid = (lo + hi) >> 1;
        if (check(mid)) {
            ans = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    cout << ans << "\n";
    return 0;
}