uva_11019 Matrix Matcher

题目:

  给定一个 的矩阵和一个 的矩阵,求后者在前者中出现了多少次。

思路:

  在二维数组上哈希,可以一行一行对格子编号。第 的权值就等于 。再做一次二维前缀和,查询枚举一个端点即可。一个特别要注意的点, 的矩阵的编号应为在第一个矩阵中对应的点,这样才能把第二个矩阵移到枚举的位置进行比较。复杂度

代码:

#include <bits/stdc++.h>
#define _(...) (void)(__VA_ARGS__)
#define rep(i,a,b) for(int i(a),i##_END_(b);i<=i##_END_;i++)
#define drep(i,a,b) for(int i(a),i##_END_(b);i>=i##_END_;i--)
template<class T> inline bool tomax(T &a,T b){return a<b?a=b,1:0;}
template<class T> inline bool tomin(T &a,T b){return b<a?a=b,1:0;}
typedef long long ll;
const int N=1e3+5,MOD[3]={(int)(1e9+7),(int)(1e9+9),19260817};

int Hash[3][N][N],n,m;
char s[N][N],c[N][N];
int get(int x1,int y1,int x2,int y2,int d){
    int ans=Hash[d][x2][y2];
    ans=((ll)ans-Hash[d][x2][y1-1]-Hash[d][x1-1][y2]+Hash[d][x1-1][y1-1])%MOD[d];
    return (ans+MOD[d])%MOD[d];
}

int prd[3][N][N];

int main(){
    int cas,x,y;
    scanf("%d",&cas);
    while(cas--){
        scanf("%d%d",&n,&m);
        rep(i,1,n)
            scanf("%s",s[i]+1);
        scanf("%d%d",&x,&y);
        rep(i,1,x)
            scanf("%s",c[i]+1);
        int ans[]={0,0,0};
        rep(k,0,2){
            int p=1;
            rep(i,1,n)
                rep(j,1,m){
                    int val=(ll)p*(s[i][j]-'a'+1)%MOD[k];
                    Hash[k][i][j]=((ll)val+Hash[k][i-1][j]+Hash[k][i][j-1]-Hash[k][i-1][j-1])%MOD[k];
                    Hash[k][i][j]=(Hash[k][i][j]+MOD[k])%MOD[k];
                    if(i<=x&&j<=y)
                        (ans[k]+=(ll)p*(c[i][j]-'a'+1)%MOD[k])%=MOD[k];
                    prd[k][i][j]=p;
                    p=p*29ll%MOD[k];
                }
        }
        int out=0;
        rep(i,x,n)
            rep(j,y,m){
                bool flag=true;
                rep(k,0,2)
                    flag&=(get(i-x+1,j-y+1,i,j,k)==(ll)ans[k]*prd[k][i-x+1][j-y+1]%MOD[k]);
                out+=flag;
            }
        printf("%d\n",out);
    }
    return 0;
}