存代码

[USACO17OPEN] Bovine Genomics G

#include<bits/stdc++.h>
#define int long long
#define maxm 0X66CCFF
#define N 510
namespace IO{
    inline void close(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);}
    inline void Fire(){freopen(".in","r",stdin);freopen(".out","w",stdout);}
    inline int read(){int s = 0,w = 1;char ch = getchar();while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();}while(ch>='0'&&ch<='9'){ s=(s<<3)+(s<<1)+ch-'0';ch = getchar();}return s*w;}
    inline void write(int x){char F[200];int tmp=x>0?x:-x,cnt=0;;if(x<0)putchar('-') ;while(tmp>0){F[cnt++]=tmp%10+'0';tmp/=10;}if(cnt==0)putchar('0');while(cnt>0)putchar(F[--cnt]);putchar(' ');}
}
using namespace IO;
using namespace std;
const int P1=315716251,P2=475262633;
int a,b;
struct Hash{
    int h1[N],h2[N],z1[N],z2[N];
    inline void Init(const char *s){
        int n=strlen(s+1);
        const int b=131;
        z1[0]=z2[0]=1;
        for(register int i=1;i<=n;i++){
            z1[i]=z1[i-1]*b%P1;
            z2[i]=z2[i-1]*b%P2;
            h1[i]=(h1[i-1]*b+(s[i]-'A'+1%P1))%P1;
            h2[i]=(h2[i-1]*b+(s[i]-'A'+1%P2))%P2;
        }
    }
    inline int Get1(int l,int r){
        return (h1[r]-h1[l-1]*z1[r-l+1]%P1+P1)%P1;
    }
    inline int Get2(int l,int r){
        return (h2[r]-h2[l-1]*z2[r-l+1]%P2+P2)%P2;
    }
}aaa[N],bbb[N];
map<long long,bool> mp1,mp2;
inline bool Check(int n){
    for(register int i=n;i<=b;++i){
        bool f=1;
        mp1.clear(),mp2.clear();
        for(register int j=1;j<=a;++j){
            mp1[aaa[j].Get1(i-n+1,i)]=true;
            mp2[aaa[j].Get1(i-n+1,i)]=true;
        }
        for(register int j=1;j<=a;++j){
            if(mp1[bbb[j].Get1(i-n+1,i)]) f=0;
            if(mp2[bbb[j].Get1(i-n+1,i)]) f=0;
        }
        if(f) return true;
    }
    return false;
}
char aa[510][510];
char bb[510][510];
signed main(){
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif
    a=read(),b=read();
    for(register int i(1);i<=a;++i){
        scanf("%s",aa[i]+1);
        aaa[i].Init(aa[i]);
    }
    for(register int i(1);i<=a;++i){
        scanf("%s",bb[i]+1);
        bbb[i].Init(bb[i]);
    }
    int l(1),r(b);
    while(l<r){
        int mid((l+r)>>1);
        if(Check(mid))r=mid;
		else l=mid+1;
    }
    write(l);
}