Bovine Genomics

虽然 $N,M$ 并不大，但直接用字符串比较和set还是会TLE的，所以需要用到字符串哈希。用了哈希之后，如果求最小范围的时候使用所有 $M^2$ 个范围去试，还是会有两个case TLE。这时我们观察到范围具有单调性，如果一个范围可以，则包含它的更大范围肯定也可以，倒过来，如果一个范围不可以，那它的子范围也不行。所以我们可以用two pointers的办法来解，降低一维 $M$ 的复杂度，最后是 $\mathcal{O}(NM)$ 复杂度。

从单调性考虑，当然也可以使用二分的办法来做，这样比two pointers多一个 $\log M$ ，也是可以过的。

官方题解使用了一个基于随机数的更简单的哈希函数，程序更短，也可以参考。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n, m;
char s[1005][505];  // [2N][M]
int h[1005][505], p[505];
const int A = 911382323, M = 972663749;
 
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < 2*n; i++)
        scanf("%s", s[i]);
    
    p[0] = 1; 
    for (int i = 1; i < m; i++)
        p[i] = (ll)p[i-1] * A % M;
    for (int i = 0; i < 2*n; i++) {
        h[i][0] = s[i][0];
        for (int j = 1; j < m; j++)
            h[i][j] = ((ll)h[i][j-1] * A + s[i][j]) % M;
    }
    auto hsh = [](int i, int a, int b) -> int {
        int res;
        if (a == 0) res = h[i][b];
        else res = (h[i][b] - (ll)h[i][a-1] * p[b-a+1] + (ll)h[i][a-1] * M) % M;
        // printf("h[%d,%d,%d]=%d\n", i, a, b, res);
        return res;
    };
 
    int ans = 1e9;
    int i = 0;                  // left border
    for (int j = 0; j < m; ) {  // right border
        unordered_set<int> spotty;
        bool ok = true;
        for (int k = 0; k < n; k++)
            spotty.insert(hsh(k, i, j));
        for (int k = n; k < 2*n; k++)
            if (spotty.find(hsh(k,i,j)) != spotty.end()) {
                ok = false;
                break;
            }
        if (ok) {
            ans = min(ans, j-i+1);
            i++;
            if (i > j) j++;
        } else j++;
    }
    printf("%d", ans == 1e9 ? -1 : ans);
 
    return 0;
}