BZOJ2462--二维Hash

#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值 
		}
	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\n");
		else 
		     printf("0\n");		
	}
	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