Ural 1486 Equal squares
给出一个N*M的字符矩阵,请找出两个一模一样的K*K的矩形.
Input
第一行给出N,M,其小于等于500 下面N行M列用来描述这个字符矩阵.其由小写字母组成.
Output
最大的K值.
Sample Input
aaa
aaa
baa
Sample Output
2
//找到的两个矩阵的左上角坐标分为(1,1),(2,2).它们的大小为2
Sol:二分答案再二维Hash
#include<cstdio>
#include<algorithm>
#define N 510
typedef unsigned long long ll;
const ll D1=97,D2=131;
int n,m,i,j,l,r,mid,ans,t;
char a[N][N];ll pow1[N],pow2[N],h[N][N],tmp,tmp2,hash[N*N];
bool check(int x)
{
for(i=1;i<=n;i++) //枚举行
{
for(tmp=0,j=1;j<x;j++) //枚举列
tmp=tmp*D1+a[i][j],h[i][j]=0;
for(j=x;j<=m;j++)
h[i][j]=tmp=tmp*D1-pow1[x]*a[i][j-x]+a[i][j];
}
for(t=0,i=x;i<=m;i++)
{
for(tmp=0,j=1;j<x;j++)
tmp=tmp*D2+h[j][i];
for(j=x;j<=n;j++)
hash[t++]=tmp=tmp*D2-pow2[x]*h[j-x][i]+h[j][i];
}
for(std::sort(hash,hash+t),i=1;i<t;i++)
if(hash[i-1]==hash[i])
return 1;
return 0;
}
int main(){
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
for(scanf("%s",a[i]+1),j=1;j<=m;j++)
a[i][j]-='a'-1;
l=1,r=n<m?n:m;
for(pow1[0]=pow2[0]=i=1;i<=r;i++)
pow1[i]=pow1[i-1]*D1,pow2[i]=pow2[i-1]*D2;
while(l<=r)
if(check(mid=(l+r)>>1))
l=(ans=mid)+1;
else
r=mid-1;
printf("%d",ans);
}
ZZ:
https://blog.csdn.net/zhhx2001/article/details/52160886
BZOJ2462
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
typedef unsigned int ull;
typedef long long ll;
const int base1=2;//base 取质数，这两个质数不能相同
const int base2=9191891;
int n,m,nn,mm;
unsigned int a[1005][1005],qb1[1005],qb2[1005],hs[1000509],tot;
char mp[1005][1005];
int main()
{
scanf("%d%d%d%d",&n,&m,&nn,&mm);
qb1[0]=qb2[0]=1;
for (int i=1;i<=1003;i++)
qb1[i]=qb1[i-1]*base1,
qb2[i]=qb2[i-1]*base2;
for (int i=1;i<=n;i++) //读入文本字符矩阵
scanf("%s",mp[i]+1);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
a[i][j]=a[i][j-1]*base1+mp[i][j]-'0';
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
a[i][j]=a[i-1][j]*base2+a[i][j];
for (int i=nn;i<=n;i++)
for (int j=mm;j<=m;j++)
{
unsigned int hss=
a[i][j]-
a[i][j-mm]*qb1[mm]-
a[i-nn][j]*qb2[nn]+
a[i-nn][j-mm]*qb1[mm]*qb2[nn];
hs[++tot]=hss;//二维差分取hash值 ,qb1是记录每一行某一列时的base1的若干次方。
}
sort(hs+1,hs+tot+1);
memset(a,0,sizeof(a));
int tt=0,q;
scanf("%d",&q);
for (int i=1;i<=q;i++)
{
for (int i=1;i<=nn;i++)
scanf("%s",mp[i]+1);
for (int i=1;i<=nn;i++)
for (int j=1;j<=mm;j++)
a[i][j]=a[i][j-1]*base1+mp[i][j]-'0';
for (int i=1;i<=nn;i++)
for (int j=1;j<=mm;j++)
a[i][j]=a[i-1][j]*base2+a[i][j];
int k=lower_bound(hs+1,hs+tot+1,a[nn][mm])-hs;
if (hs[k]==a[nn][mm])
printf("1
");
else
printf("0
");
}
return 0;
}
//https://blog.csdn.net/zhhx2001/article/details/52160886
#include<bits/stdc++.h>
#define MAX 1100
using namespace std;
const unsigned int BASE1 = 10016957;
const unsigned int BASE2 = 10016957;
const int MO = 99999997;
int m,n,ask_m,ask_n,asks;
unsigned int hash[MAX][MAX],_hash[MAX][MAX];
unsigned int pow1[MAX],pow2[MAX];
bool set[100000000];
inline unsigned int GetHash()
{
for(int i = 1; i <= ask_m; ++i)
for(int j = 1; j <= ask_n; ++j)
_hash[i][j] += _hash[i - 1][j] * BASE1;
for(int i = 1; i <= ask_m; ++i)
for(int j = 1; j <= ask_n; ++j)
_hash[i][j] += _hash[i][j - 1] * BASE2;
return _hash[ask_m][ask_n];
}
int main()
{
cin >> m >> n >> ask_m >> ask_n;
for(int i = 1; i <= m; ++i)
for(int j = 1; j <= n; ++j)
scanf("%1d",&hash[i][j]);
pow1[0] = pow2[0] = 1;
for(int i = 1; i <= 100; ++i)
pow1[i] = pow1[i - 1] * BASE1,pow2[i] = pow2[i - 1] * BASE2;
for(int i = 1; i <= m; ++i)
for(int j = 1; j <= n; ++j)
hash[i][j] += hash[i - 1][j] * BASE1;
for(int i = 1; i <= m; ++i)
for(int j = 1; j <= n; ++j)
hash[i][j] += hash[i][j - 1] * BASE2;
for(int i = ask_m; i <= m; ++i)
for(int j = ask_n; j <= n; ++j) {
unsigned int h = hash[i][j];
h -= hash[i - ask_m][j] * pow1[ask_m];
h -= hash[i][j - ask_n] * pow2[ask_n];
h += hash[i - ask_m][j - ask_n] * pow1[ask_m] * pow2[ask_n];
set[h % MO] = true;
}
for(cin >> asks; asks--;) {
for(int i = 1; i <= ask_m; ++i)
for(int j = 1; j <= ask_n; ++j)
scanf("%1d",&_hash[i][j]);
puts(set[GetHash() % MO] ? "1":"0");
}
return 0;
}
//https://blog.csdn.net/Devil_Gary/article/details/78295162