UVA11019 Matrix Matcher

· · 题解

UVA11019 Matrix Matcher

上午模拟赛赛题，同机房串串大佬用 KMP 切了，我不会 KMP，故来一发哈希题解。

简要题意

给定字符矩阵 A,B，求 B 在 A 中出现的次数。

思路

我不会 KMP，遂考虑哈希。

如何计算一个矩阵的哈希值呢？模仿二维前缀和的思路，二维前缀和初始化的式子是：

sum_{i,j} = sum_{i - 1, j} + sum_{i,j - 1} - sum_{i - 1, j - 1} + a_{i,j}

然后就能以类前缀和的思路写出哈希值了，令 h_{i,j} 表示 A 矩阵从 (1,1) 到 (i,j) 组成的字符矩阵的哈希值（下标从 1 开始）。B 矩阵同理。

初始化时类似于二维前缀和，只不过每次转移要乘上 base 的权值，不难得到式子：

h_{i,j} = h_{i-1,j} \times base_1 + h_{i,j - 1} \times base_2 - h_{i-1,j-1} \times base_1 \times base_2 + A_{i,j}

注意从前往后转移和从上到下转移一定要用两个不同的 base。考虑这样的数据：

abc
bac
cab

这样的话 h_{1,3} = h_{3,1}，但这两个矩阵并不相等，出现冲突，所以要用两个 base。

然后考虑子矩阵的哈希值怎么计算。

红色的是待求矩阵，很轻易的得出哈希式子，令 \operatorname{hash}(x,y,i,j) 表示从 (x,y) 到 (i,j) 组成的矩阵的哈希值。

\operatorname{hash}(x,y,i,j) = h_{i,j} - h_{x,y} \times base_1^x \times base_2^y + h_{i,y} \times base_2^y + h_{x,j} \times base_1^x

式子可以结合上图理解。

然后所有的式子都推出来了，然后注意相似的变量名不要写错了。

我怕哈希被卡所以取了比较小众的模数，然后取两个 base 即可。

代码如下：

#define mod 920121431
#define base 131
#define base2 2113
#define int ll

void init(){
    memset(h, 0, sizeof h);
    memset(h2, 0, sizeof h2);
    memset(p, 0, sizeof p);
    memset(q, 0, sizeof q);

    p[0] = q[0] = 1;
    for(int i = 1; i <= n; i++)
        p[i] = p[i - 1] * base % mod;
    for(int i = 1; i <= m; i++)
        q[i] = q[i - 1] * base2 % mod;
}

void hashing(){
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            h[i][j] = ((h[i - 1][j] * base % mod + h[i][j - 1] * base2 % mod) % mod -
                        h[i - 1][j - 1] * base % mod * base2 % mod + mod) % mod + a[i][j];

    for(int i = 1; i <= x; i++)
        for(int j = 1; j <= y; j++)
            h2[i][j] = ((h2[i - 1][j] * base % mod + h2[i][j - 1] *base2 % mod) % mod -
                         h2[i - 1][j - 1] * base % mod * base2 % mod + mod) % mod + b[i][j];
}

int gethash(int rx, int ry, int lx, int ly){
    int res = ((h[rx][ry] - h[rx - lx][ry] * p[lx] % mod + mod - h[rx][ry - ly] * q[ly] % mod +
                mod + h[rx - lx][ry - ly] * p[lx] % mod * q[ly] % mod) % mod + mod) % mod;
    return res;
}

void solve(){
    cin >> n >> m;
    init();
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> a[i][j];

    cin >> x >> y;
    for(int i = 1; i <= x; i++)
        for(int j = 1; j <= y; j++)
            cin >> b[i][j];

    hashing();
    int ans = 0;

    for(int i = x; i <= n; i++){
        for(int j = y; j <= m; j++){
            int t1 = gethash(i, j, x, y);
            int t2 = h2[x][y];
            if(t1 == t2)
                ans++;
        }
    }
    cout << ans << endl;
}

代码写的丑见谅。

不过这题似乎可以自然溢出，这样代码会好看一些。