专栏文章

UVA11019 Matrix Matcher

___Charlie_Chen__
UVA11019题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@min022ru
此快照首次捕获于
2025/12/01 18:21
3 个月前
此快照最后确认于
2025/12/01 18:21
3 个月前
查看原文

UVA11019 Matrix Matcher

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

简要题意

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

思路

我不会 KMP，遂考虑哈希。
如何计算一个矩阵的哈希值呢？模仿二维前缀和的思路，二维前缀和初始化的式子是：
sumi,j=sumi−1,j+sumi,j−1−sumi−1,j−1+ai,jsum_{i,j} = sum_{i - 1, j} + sum_{i,j - 1} - sum_{i - 1, j - 1} + a_{i,j}
然后就能以类前缀和的思路写出哈希值了，令 hi,jh_{i,j} 表示 AA 矩阵从 (1,1)(1,1) 到 (i,j)(i,j) 组成的字符矩阵的哈希值（下标从 11 开始）。BB 矩阵同理。
初始化时类似于二维前缀和，只不过每次转移要乘上 basebase 的权值，不难得到式子：
hi,j=hi−1,j×base1+hi,j−1×base2−hi−1,j−1×base1×base2+Ai,jh_{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}
注意从前往后转移和从上到下转移一定要用两个不同的 basebase。考虑这样的数据：
PLAIN
abc
bac
cab
这样的话 h1,3=h3,1h_{1,3} = h_{3,1}，但这两个矩阵并不相等，出现冲突，所以要用两个 basebase。
然后考虑子矩阵的哈希值怎么计算。
红色的是待求矩阵，很轻易的得出哈希式子，令 hash⁡(x,y,i,j)\operatorname{hash}(x,y,i,j) 表示从 (x,y)(x,y) 到 (i,j)(i,j) 组成的矩阵的哈希值。
hash⁡(x,y,i,j)=hi,j−hx,y×base1x×base2y+hi,y×base2y+hx,j×base1x\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
式子可以结合上图理解。
然后所有的式子都推出来了，然后注意相似的变量名不要写错了。
我怕哈希被卡所以取了比较小众的模数，然后取两个 basebase 即可。
代码如下：
CPP
#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;
}
代码写的丑见谅。
不过这题似乎可以自然溢出，这样代码会好看一些。

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...