Matrix（二维hash）

题目链接

@[toc]

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

给定一个M行N列的01矩阵（只包含数字0或1的矩阵），再执行Q次询问，每次询问给出一个A行B列的01矩阵，求该矩阵是否在原矩阵中出现过。
输入描述: 第一行四个整数M,N,A,B。 接下来一个M行N列的01矩阵，数字之间没有空格。 接下来一个整数Q。
接下来Q个A行B列的01矩阵，数字之间没有空格。 输出描述: 对于每个询问，输出1表示出现过，0表示没有。

示例1
输入

3 3 2 2
111
000
111
3
11
00
11
11
00
11

输出

1
0
1

备注:
对于40%的数据，A = 1。
对于80%的数据，A≤10。
对于100%的数据，A≤100，M,N≤1000，Q≤1000。

题意：

给你个MN的二维矩阵，然后给你个AB的二维矩阵，问后者是否在前者出现过

题解

毫无疑问用hash
我们先想一个问题：
一个长为L的字符串a，问长度为len（len<L）的字符串b在a中出现过吗？
这个怎么做？
我们可以将a中长度为len的部分求出hash并放进哈希表，然后求出b的hash，进行比较即可

其实本题就是将一维问题转化成二维
我们将n * m的矩形中所有大小为a * b的矩形哈希一下并放到哈希表中，然后给出矩阵后，直接O（1）查找就可以了
求矩阵的hash的步骤：
先求出每一行前缀的hash，然后固定矩阵的一边长度b，求出长度为b的边的hash值，然后从这一行向下延伸a行，求出这a行对应的长度为b的hash值。当长度大于a后，就将最上面一行删去，始终保持为 a * b 的矩阵。

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn=1005;
typedef unsigned long long ull;
ull hash1[maxn][maxn];
ull base[maxn*maxn];
int base1=13;
char c[maxn];
ull get(ull hash1[],int l,int r)
{
    return hash1[r]-hash1[l-1]*base[r-l+1];
}
int q;
int n,m,a,b;
int main(){

    cin>>n>>m>>a>>b;
    base[0]=1;
    for(int i=1;i<=n*m;i++) base[i]=base[i-1]*base1;//素数倍数，用于查询子串哈希值 

    for(int i=1;i<=n;i++)
    {
        scanf("%s",c+1);
        for(int j=1;j<=m;j++) hash1[i][j]=hash1[i][j-1]*base1+c[j]-'0';//求取每一行前缀哈希值 
    }
    unordered_set<ull> s;
    for(int i=b;i<=m;i++)
    {
        ull x=0;
        int l=i-b+1,r=i;
        for(int j=1;j<=n;j++)
        {
            x=x*base[b]+get(hash1[j],l,r);// 加上当前行的hash值 
            if(j>a) x-=get(hash1[j-a],l,r)*base[a*b];// 如果超行了，删去最上面一行 
            if(j>=a)
            {
                s.insert(x);//用map来存哈希值，方便后面的判断是否存在 
            }
        }
    }

    cin>>q;
    while(q--)
    {
        ull x=0;
        for(int i=0;i<a;i++)
        {
            scanf("%s",c);
            for(int j=0;j<b;j++)
            {
                x=x*base1+c[j]-'0';//将所给的矩阵转化成hash 
            }
        }
        if(s.count(x))//利用map性质查询是否有这个数 
        cout<<"1"<<endl;
        else cout<<"0"<<endl;
    }
    return 0;
}

不过这样做，好像超内存了。。。
可以手写map会好些

借鉴其他大佬代码

#include<bits/stdc++.h>
const int N=1000;
const int BASE1=10016957;
const int BASE2=10016959;
const int Mod=10100;
typedef unsigned int ui;
using namespace std;
struct abcd
{
    unsigned num;
    int next;
} table[N*N+5];
int m,n,a,b,q;
ui sum[N+5][N+5],power1[N+5],power2[N+5];
int hash_table[Mod],tot;
void Hash(ui x)
{
    int pos=x%Mod;
    table[++tot].num=x;
    table[tot].next=hash_table[pos];
    hash_table[pos]=tot;
}
bool Get_Hash(ui x)
{
    int pos=x%Mod;
    for(int i=hash_table[pos]; i; i=table[i].next)
        if(table[i].num==x)
            return true;
    return false;
}
int main()
{
    scanf("%d%d%d%d",&m,&n,&a,&b);
    for(int i=1; i<=m; i++)
        for(int j=1; j<=n; j++)
            scanf("%1d",&sum[i][j]);
    for(int i=1; i<=m; i++)
        for(int j=1; j<=n; j++)
            sum[i][j]+=sum[i-1][j]*BASE1;
    for(int i=1; i<=m; i++)
        for(int j=1; j<=n; j++)
            sum[i][j]+=sum[i][j-1]*BASE2;
    power1[0]=power2[0]=1;
    for(int i=1; i<=N; i++)
        power1[i]=power1[i-1]*BASE1,power2[i]=power2[i-1]*BASE2;
    for(int i=a; i<=m; i++)
        for(int j=b; j<=n; j++)
        {
            ui temp=sum[i][j]-sum[i-a][j]*power1[a]-sum[i][j-b]*power2[b]+sum[i-a][j-b]*power1[a]*power2[b];
            Hash(temp);
        }
    scanf("%d",&q);
    while(q--)
    {
        for(int i=1; i<=a; i++)
            for(int j=1; j<=b; j++)
                scanf("%1d",&sum[i][j]);
        for(int i=1; i<=a; i++)
            for(int j=1; j<=b; j++)
                sum[i][j]+=sum[i-1][j]*BASE1;
        for(int i=1; i<=a; i++)
            for(int j=1; j<=b; j++)
                sum[i][j]+=sum[i][j-1]*BASE2;
        ui temp=sum[a][b];
        if(Get_Hash(temp))
            puts("1");
        else
            puts("0");
    }
    return 0;
}