USACO 2017 US Open Contest Gold T1: Bovine Genomics

题目大意

FJ有一些有斑点和一些没有斑点的牛，他想搞清楚到底什么基因控制这个牛有没有斑点。

于是他找了n (有斑点的牛和n头没有斑点的牛

这些牛的基因长度为m(（基因中之包含ATCG四个字母）

求这个序列中的一个子串，可以确定是否有斑点。

子串需要符合要求：有斑点的牛这部分的子串，不能和无斑点的牛的这部分子串相同

求最短子串长度

题目分析

题目让我们找的就是一个最短子串长度使得它在有斑点的牛中的那些段都没在没有斑点的牛中出现过。

要判断淄川是否相同，可以使用蛤希。

我们递推左端点 i 与右端点 j。

用d记录不同的个数，同时用一个set来去重。

若d已经为0了，我们就开始从左往右推 i ,否则就继续向右推 j, 直到不同。

更多细节详见代码。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int MAXN=505;
 4 typedef unsigned long long ull;
 5 const ull Base=233;
 6 
 7 int n,m;
 8 string s[MAXN],p[MAXN]; 
 9 ull hsh1[MAXN],hsh2[MAXN],r[MAXN];
10 int main(){
11     scanf("%d%d",&n,&m);
12     for(int i=1;i<=n;++i) cin>>s[i];
13     for(int i=1;i<=n;++i) cin>>p[i];
14     r[0]=Base;
15     for(int i=1;i<=m;++i) r[i]=r[i-1]*Base;
16     
17     int i=0,j=0;
18     int ans=m,d=n;
19     while(j<m){
20         if(d==0) ans=min(ans,j-i);
21         
22         if(d>0){
23             d=0;
24             set<int> ss;
25             for(int k=1;k<=n;++k)
26                 ss.insert(hsh1[k]+=r[j]*s[k][j]);
27             for(int k=1;k<=n;++k)
28                 if(ss.count(hsh2[k]+=r[j]*p[k][j])>0) 
29                     ++d;
30             ++j;
31         }
32         else{
33             d=0;
34             set<int> ss;
35             for(int k=1;k<=n;++k)
36                 ss.insert(hsh1[k]-=r[i]*s[k][i]);
37             for(int k=1;k<=n;++k)
38                 if(ss.count(hsh2[k]-=r[i]*p[k][i])>0)
39                     ++d;
40             ++i;
41         }
42     }
43     printf("%d
",ans);
44     return 0;
45 }