二维hash的时候可以把每一行的都看成是一个元素,对于a乘b的矩阵我们把第i行往下挪一行的时候,那么每一行都要乘上b,即每个元素往后挪b位让整体往下挪1行,然后再加上第i+1行的hash值,最后再剪去第1行的
C++ 代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<unordered_set>
using namespace std;
typedef unsigned long long ull;
const int N=1e3+10,M=N*N,INF=1e8,P=131;
int n,m,a,b;
char str[N];
ull h[N][N],p[M];
ull get(ull h[],int l,int r)a
{
return h[r]-h[l-1]*p[r-l+1];
}
int main()
{
cin>>n>>m>>a>>b;
p[0]=1;
for(int i=1;i<=n*m;i++) p[i]=p[i-1]*P;
for(int i=1;i<=n;i++)
{
cin>>str+1;
for(int j=1;j<=m;j++)
{
h[i][j]=h[i][j-1]*P+str[j];
}
}
unordered_set<ull>S;
for(int i=b;i<=m;i++)
{
ull s=0;
int l=i-b+1,r=i;
for(int j=1;j<=n;j++)
{
s=s*p[b]+get(h[j],l,r);
if(j>a) s-=get(h[j-a],l,r)*p[a*b];
if(j>=a) S.insert(s);
}
}
int q;
cin>>q;
while(q--)
{
ull s=0;
for(int i=1;i<=a;i++)
{
cin>>str+1;
for(int j=1;j<=b;j++)
{
s=s*P+str[j];
}
}
if(S.count(s)) cout<<"1"<<endl;
else cout<<"0"<<endl;
}
return 0;
}