UVA11019 Matrix Matcher 记录

· · 题解

题意：给一个字母矩阵，进行一次询问，询问给定一个矩阵，问询问的矩阵在原矩阵里匹配上了几次。

考虑 \text{YY} 出一个二维 \text{Hash}

记一个矩阵 a 的哈希值为

\sum_{i=1}^n\sum_{j=1}^ma_{i,j}b_1^{n-i}b_2^{m-j}

那么类似一维哈希，一个 (x_1,y_1) 到 (x_2,y_2) 的矩阵的哈希值为

H(x_2,y_2)-H(x_1-1,y_2)b_1^{x_2-x_1+1}-H(x_2,y_1-1)b_2^{y_2-y_1+1}+ H(x_1-1,y_1-1)b_1^{x_2-x_1+1}b_2^{y_2-y_1+1}

对于存哈希值你可以不用 \text{map} ，你可以直接塞进一个数组里，然后统一排序，但不要去重，询问存在几次就直接用

upper_bound(range,x)-lower_bound(range,x)

就行了

#define maxn 1010
typedef unsigned long long ull;
int n,m,a,b,T;
char s[maxn][maxn];
ull u1=131,u2=13331;
ull pw1[maxn],pw2[maxn];
ull f[maxn][maxn];
ull H(int n,int m,int s,int l){
    return f[s][l]-f[n-1][l]*pw1[s-n+1]-f[s][m-1]*pw2[l-m+1]+f[n-1][m-1]*pw1[s-n+1]*pw2[l-m+1];
}
ull S[maxn*maxn],cnt;
signed main(){
#ifndef ONLINE_JUDGE
    freopen("testdata.in","r",stdin);
#endif
    for(cin>>T;T;T--){
        cin>>n>>m;
        for(int i=1;i<=n;i++)cin>>s[i]+1;
        cin>>a>>b;
        pw1[0]=pw2[0]=1;
        for(int i=1;i<=n;i++)pw1[i]=pw1[i-1]*u1;
        for(int i=1;i<=m;i++)pw2[i]=pw2[i-1]*u2;
        for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        f[i][j]=f[i-1][j]*u1+f[i][j-1]*u2+(s[i][j]-'a')-f[i-1][j-1]*u1*u2;
        cnt=0;
        for(int i=1;i<=n-a+1;i++)
        for(int j=1;j<=m-b+1;j++)
        S[++cnt]=H(i,j,i+a-1,j+b-1);
        sort(S+1,S+cnt+1);
        for(int i=1;i<=a;i++)cin>>s[i]+1;
        for(int i=1;i<=a;i++)
        for(int j=1;j<=b;j++)
        f[i][j]=f[i-1][j]*u1+f[i][j-1]*u2+(s[i][j]-'a')-f[i-1][j-1]*u1*u2;
        cout<<upper_bound(S+1,S+cnt+1,f[a][b])-lower_bound(S+1,S+cnt+1,f[a][b])<<endl;
    }
#ifndef ONLINE_JUDGE
    cerr<<endl<<(double)clock()/CLOCKS_PER_SEC;
#endif
}