「USACO17OPEN」Bovine Genomics

题意：
农夫约翰拥有 $N$ 头带斑点的奶牛和 $N$ 头没有斑点的奶牛。他刚刚完成了牛遗传学课程，他确信奶牛上的斑点是由牛基因组突变引起的。

农夫约翰花了大钱对他奶牛的基因组进行测序。每个基因组都是一串长度为 $M$ 的字符串，由四个字符 A，C，G 和 T 构成。当他排列奶牛的基因组时，他得到一张如下表，如下所示：

对于 $N = 3$ 和 $M = 8$：

$\text{Positions}$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$
$\text{Spotty Cow 1}$	$\text{A}$	$\text{A}$	$\text{T}$	$\text{C}$	$\text{C}$	$\text{C}$	$\text{A}$	$\text{T}$
$\text{Spotty Cow 2}$	$\text{A}$	$\text{C}$	$\text{T}$	$\text{T}$	$\text{G}$	$\text{C}$	$\text{A}$	$\text{A}$
$\text{Spotty Cow 3}$	$\text{G}$	$\text{G}$	$\text{T}$	$\text{C}$	$\text{G}$	$\text{C}$	$\text{A}$	$\text{A}$
$\text{Plain Cow 1}$	$\text{A}$	$\text{C}$	$\text{T}$	$\text{C}$	$\text{C}$	$\text{C}$	$\text{A}$	$\text{G}$
$\text{Plain Cow 2}$	$\text{A}$	$\text{C}$	$\text{T}$	$\text{C}$	$\text{G}$	$\text{C}$	$\text{A}$	$\text{T}$
$\text{Plain Cow 3}$	$\text{A}$	$\text{C}$	$\text{T}$	$\text{T}$	$\text{C}$	$\text{C}$	$\text{A}$	$\text{T}$

他仔细查看该表，认为从位置 $2$ 到位置 $5$ 的顺序足以解释斑点。也就是说，仅通过查看这些位置（即位置 $2\sim 5$）中的字符，农夫约翰就可以预测出他的哪些母牛斑点，哪些不是斑点。例如，如果他在这些位置看到字符 GTCG，他就知道那头母牛一定是斑点的。

请帮助 FJ 找到可以解释斑点的最短位置序列的长度。

简单二分 + hash 一下即可。

把每个字符串拿出来处理一下，二分长度，把 hash 值放进 set，找一下即可。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<set>
#include<algorithm>
#define INF 1e9
using namespace std;
const int maxn=510,mod=1e9+7;
int n,m,ans,seed=37;
char s[maxn][maxn],t[maxn][maxn];
long long hash1[maxn][maxn],hash2[maxn][maxn];
set<long long> p;
long long power(long long a,long long b,long long p)
{
	long long ans=1%p;
	for(;b;b>>=1)
	{
		if(b&1)
			ans=ans*a%p;
		a=a*a%p;
	}
	return ans%p;
}
bool check(int len)
{
	int id=0;
	for(int i=1;i+len-1<=m;i++)
	{
		p.clear();
		int flag=0;
		int j=i+len-1;
		for(int k=1;k<=n;k++)
			p.insert((hash1[k][j]-hash1[k][i-1]*power(seed,j-i+1,mod)+mod)%mod);//添加第一组的hash值
		for(int k=1;k<=n;k++)
			if(p.find((hash2[k][j]-hash2[k][i-1]*power(seed,j-i+1,mod)+mod)%mod)!=p.end())//在第二组中是否能找到
			{
				flag=1;//找到答案
				break;
			}
		if(!flag)
		{
			id=1;
			break;
		}
	}
	return id;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%s",s[i]+1);
	for(int i=1;i<=n;i++)
		scanf("%s",t[i]+1);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			hash1[i][j]=(hash1[i][j-1]*seed+s[i][j])%mod;
			hash2[i][j]=(hash2[i][j-1]*seed+t[i][j])%mod;
		}
	int l=1,r=m;
	while(l<r)
	{
		int mid=(l+r)>>1;
		if(check(mid))
		{
			r=mid;
			ans=mid;
		}
		else
			l=mid+1;
	}
	printf("%d",ans);
	return 0;
}