砂金听说了你在学字符串，于是在CLOI里出了道题给你
P3667 Bovine Genomics
\(hash\)基础题。
思路是二分答案，\(check\)中比较每一个区间字串的\(hash\)值是否相等。
比较的时候可以用\(set\)或\(map\)。
\(set\)的好处在于无重元素，判断时先将\(a\)串中区间子串的哈希值放入数组，再用\(find\)函数，每次寻找\(b\)串的区间子串的哈希值是否出现过。我个人用的\(set\)，代码在下面。
\(map\)的话写起来差不多，值类型设为\(bool\)，每次直接判断\(true\,or\,false\)即可。
代码如下：
map<ull,bool>m;
bool check(int len)
{
int re=0;
for(int i=1;i+len-1<=m;i++)
{
bool kk=false;
m.clear();
int j=i+len-1;
fo(k,1,n)
m[Aget_hash(i,j,k,1)]=true;
fo(k,1,n)
if(m[Aget_hash(i,j,k,0)])
{
kk=true;
break;
}
if(!kk)
{
re=1;
break;
}
}
return re;
}
完整代码：
所有
#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x)=(y);(x)>=(z);(x)--)
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
namespace Dr
{
inline int qr()
{
char ch=getchar();int x=0,f=1;
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
inline void qw(ull x)
{
if(!x)
return;
qw(x/10);
putchar(x%10+'0');
}
}
#define qr qr()
using namespace Dr;
const int Ratio=0;
const int N=1005;
const int maxi=INT_MAX;
int lena,lenb,n,m;
ull p[N],ha[N][N],hb[N][N];
char a[N][N],b[N][N];
ull base=233,ans;
namespace Acheronhash
{
void Aprepare()
{
p[0]=1;
fo(i,1,500)
p[i]=p[i-1]*base;
}
ull Aget_hash(int l,int r,int id,int x)
{
if(x)
return ha[id][r]-ha[id][l-1]*p[r-l+1];
else
return hb[id][r]-hb[id][l-1]*p[r-l+1];
}
// ull Aget_s(int l,int r,int x)
// {
// return Aget_hash(l,x-1)*p[r-x]+Aget_hash(x+1,r);
// }
ull Aget_hashall(char c[])
{
int len=strlen(c);
ull ans=0;
fo(i,0,len-1)
ans=ans*base+(ull)c[i];
return ans;
}
void Aget_hasheverya(int id)
{
fo(i,1,m)
ha[id][i]=ha[id][i-1]*base+a[id][i];
}
void Aget_hasheveryb(int id)
{
fo(i,1,m)
hb[id][i]=hb[id][i-1]*base+b[id][i];
}
}
using namespace Acheronhash;
set<ull>f;
bool check(int len)
{
int re=0;
for(int i=1;i+len-1<=m;i++)
{
bool kk=false;
f.clear();
int j=i+len-1;
fo(k,1,n)
f.insert(Aget_hash(i,j,k,1));
fo(k,1,n)
if(f.find(Aget_hash(i,j,k,0))!=f.end())
{
kk=true;
break;
}
if(!kk)
{
re=1;
break;
}
}
return re;
}
int main()
{
Aprepare();
n=qr,m=qr;
fo(i,1,n)
{
scanf("%s",a[i]+1);
Aget_hasheverya(i);
}
fo(i,1,n)
{
scanf("%s",b[i]+1);
Aget_hasheveryb(i);
}
int l=1,r=m;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid))
ans=mid,r=mid-1;
else
l=mid+1;
}
printf("%lld\n",ans);
return Ratio;
}
或一无所有
完结撒花
标签：Genomics,ch,Hash,int,题解,mid,len,long,check From： https://www.cnblogs.com/Ratio-Yinyue1007/p/18154654