Bovine Genomics (Gold)

Bovine Genomics (Gold)

思路：一开始没考虑道答案的单调性，无脑暴力超时了，菜菜菜。

因为答案具有单调性，考虑$map+$二分解决即可。

时间复杂度 ：$O(mnlogm)$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int n,m;
string a[N],b[N];
unordered_map<string,int>mp;
bool check(int x){
    for(int l=0;l+x-1<m;l++){
        mp.clear();
        int f=1;
        for(int i=1;i<=n;i++){
            mp[a[i].substr(l,x)]=1;
        }
        for(int i=1;i<=n;i++){
            if(mp[b[i].substr(l,x)]) {
                f=0;break;
            }
        }
        if(f)  return 1;
    }
    return 0;
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    cin>>n>>m;
    int ans=0;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    int l=1,r=m;
    while(l<r){
        int mid=(l+r)>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    printf("%d\n",l);
    return 0;
}