原文链接：https://blog.csdn.net/qq_38891827/article/details/80723483

UVA-11019
本体题意就是给你AB两个字符矩阵，问你B矩阵在A矩阵中的出现次数。
我们可以进行二维hash，其实就是把n个横向串连在一起hash。
注意判相等的时候，我们不断进行尺取+hash，尺取的过程，我们删除当前第一行的hash值加上最后一行的hash值，删除第一行的hash值直接删去就可以
例如
[Math Processing Error] AAAAAA
[Math Processing Error] BBBBBB
[Math Processing Error] CCCCCC
我们删去第一行的hash值 相当于把矩阵变成了
[Math Processing Error] 000000
[Math Processing Error] BBBBBB
[Math Processing Error] CCCCCC
此时我们再添加最后一行
[Math Processing Error] 000000
[Math Processing Error] BBBBBB
[Math Processing Error] CCCCCC
[Math Processing Error] DDDDDD
如果这时候的B矩阵是
[Math Processing Error] BBBBBB
[Math Processing Error] CCCCCC
[Math Processing Error] DDDDDD
这两个矩阵的hash值不同的，为了处理这种情况，我们把B矩阵相应的添加前几行
变成
[Math Processing Error] 000000
[Math Processing Error] BBBBBB
[Math Processing Error] CCCCCC
[Math Processing Error] DDDDDD
这样再去匹配就可以了。
以上就是二维hash大概的处理方法（是我自己想的做法，如果有其他好的尺取方法欢迎指教
掌握了这个做法，我们就可以枚举矩阵的左上角，然后对于当前列数的矩阵从上向下进行尺取，hash判断就可以了。

ｒｅ代码

#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn = 1e3+5;
const int MAXN = 1e6+5;
typedef unsigned long long ull;
ull hash1_[maxn][maxn],xp[MAXN],hash2_[maxn][maxn];
char str[maxn][maxn];
char str2[maxn][maxn];
void init()
{
    xp[0]=1;
    for(int i=1;i<MAXN;i++)
    {
        xp[i]=xp[i-1]*13331;
    }
    return ;
}//dai xiu gai qujian ziduan he
ull make_hash(int n,int m,char str[][maxn],ull hash_[][maxn]){
    for(int i=0;i<n;i++)
    {
        hash_[i][m]=0;
        for(int j=m-1;j>=0;j--)
        {
            hash_[i][j]=hash_[i][j+1]*13331+str[i][j]-'a'+1;//每一行分别处理hash值
        }
    }
}
ull Get_hash(int i,int j,int l,ull hash_[][maxn])
{
    return hash_[i][j]-hash_[i][j+l]*xp[l];
}
int main()
{
    init();
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int ans=0;
        int n,m,x,y;
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)
        {
            scanf("%s",str[i]);
        }
        make_hash(n,m,str,hash1_);
        scanf("%d%d",&x,&y);
        for(int i=0;i<x;i++)
            scanf("%s",str2[i]);
        make_hash(x,y,str2,hash2_);
        ull tmp=0;
        for(int i=x-1;i>=0;i--)
        {
            for(int j=y-1;j>=0;j--)
            {
                tmp=tmp*13331+str2[i][j]-'a'+1;//处理出匹配矩阵的hash值
            }
        }
//        ull tmp=0;
//        for(int j=x-1;j>=0;j--)
//        {
//            tmp=tmp*xp[y]+Get_hash(j,0,y,hash2_);
//        }
        for(int i=0;i<=m-y;i++)//枚举横坐标起点
        {
            ull tt=tmp;
            ull tmp2=0;
            for(int j=x-1;j>=0;j--)
            {
                tmp2=tmp2*xp[y]+Get_hash(j,i,y,hash1_);
            }
            if(tt==tmp2) ans++;
            for(int j=x;j<n;j++)
            {
                tmp2-=Get_hash(j-x,i,y,hash1_)*xp[(j-x)*y];//尺取过程去除第一行，也就是将第一行变为0
                tmp2+=Get_hash(j,i,y,hash1_)*xp[j*y];//加上最后一行
                tt=tt*xp[y];//将匹配矩阵第一行添上0
                if(tmp2==tt) ans++;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}