UVA 11019 Matrix Matcher（二维hash + 尺取）题解

题意：在n*m方格中找有几个x*y矩阵。

思路：二维hash，总体思路和一维差不太多，先把每行hash，变成一维的数组，再对这个一维数组hash变成二维hash。之前还在想怎么快速把一个矩阵的hash算出来，然后看到是尺取，也不知道是什么...这应该算是用到了这个思想吧。

要先预处理每行y个的hash（看代码），然后每次算出上面两顶点在第一行的hash值，慢慢往下移。hash看上去就像是在算一个seed位数一样，seed取13那么就是把字符串转化为了一个13位数，这样想可能在移动的时候更容易理解代码的含义。

代码：

#include<stack>

#include<vector>

#include<queue>

#include<set>

#include<cstring>

#include<string>

#include<sstream>

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

#define ll long long

#define ull unsigned long long

using namespace std;

const int maxn =  + ;

const int seed1 = ;

const int seed2 = ;

const int MOD = ;

const int INF = 0x3f3f3f3f;

char s[maxn][maxn],str[maxn];

ull ha[maxn][maxn];

int T;

int n, m, x, y;

int solve(ull aim){

    ull bit = ;

    for(int i = ; i <= y - ; i++)

        bit = bit * seed1;

    for(int i = ; i <= n; i++){    //预处理每一行的hash

        ull sum = ;

        for(int j = ; j <= y - ; j++){

            sum = sum * seed1 + s[i][j];

        }

        for(int j = y; j <= m; j++){

            sum = sum * seed1 + s[i][j];

            ha[i][j - y + ] = sum;

            sum -= bit * s[i][j - y + ];

        }

    }

    int ans = ;

    bit = ;

    for(int i = ; i <= x - ; i++)

        bit = bit * seed2;

    for(int j = ; j <= m - y + ; j++){

        ull sum = ;

        for(int i = ; i <= x - ; i++){

            sum = sum * seed2 + ha[i][j];

        }

        for(int i = x; i <= n; i++){

            sum = sum * seed2 + ha[i][j];

            if(sum == aim) ans++;

            sum -= bit * ha[i - x + ][j];

        }

    }

    return ans;

}

int main(){

    scanf("%d", &T);

    while(T--){

        scanf("%d%d", &n, &m);

        for(int i = ; i <= n; i++)

            scanf("%s", s[i] + );

        scanf("%d%d", &x, &y);

        ull temp, aim = ;  //先对x*y二维hash

        for(int i = ; i <= x; i++){

            scanf("%s", str + );

            temp = ;

            for(int j = ; j <= y; j++){

                temp = temp * seed1 + str[j];

            }

            aim = aim * seed2 + temp;

        }

        printf("%d\n", solve(aim));

    }

    return ;

}