求助二维哈希
查看原帖
求助二维哈希
498612
Saka_Noa楼主2023/10/4 10:44
for(int i = 1;i < N;i++) {
        c1[i] = c1[i - 1] * p1;
        c2[i] = c2[i - 1] * p2;
    }
                       
for(int i = 1;i <= n;i++) 
    for(int j = 1;j <= m;j++) 
    f1[i][j] = mp1[i][j] + f1[i][j-1]*p2 + f1[i-1][j]*p1 - f1[i-1][j-1]*p1*p2,
    f2[i][j] = mp2[i][j] + f2[i][j-1]*p2 + f2[i-1][j]*p1 - f2[i-1][j-1]*p1*p2,
    f3[i][j] = mp3[i][j] + f3[i][j-1]*p2 + f3[i-1][j]*p1 - f3[i-1][j-1]*p1*p2;
                            
bool check(int x1, int y1, int x2, int y2) {
    if(x1 < 1 || x1 > n || y1 < 1 || y1 > m) return 0;
    if(x2 < 1 || x2 > n || y2 < 1 || y2 > m) return 0;
    ull gh1 = get_hash1(x1, y1, x2, y2);
    ull gh2 = get_hash2(x1, m - y2 + 1, x2, m - y1 + 1);
    ull gh3 = get_hash3(n - x2 + 1, y1, n - x1 + 1, y2);
    return  ((gh1 == gh2) && (gh1 == gh3));
}
      
      ull get_hash1(int x1, int y1, int x2, int y2) {
    return f1[x2][y2] - f1[x1-1][y2]*c1[x2-x1+1] - f1[x2][y1-1]*c2[y2-y1+1] + f1[x1-1][y1-1]*c1[x2-x1+1]*c2[y2-y1+1]; 
}
ull get_hash2(int x1, int y1, int x2, int y2) {
    return f2[x2][y2] - f2[x1-1][y2]*c1[x2-x1+1] - f2[x2][y1-1]*c2[y2-y1+1] + f2[x1-1][y1-1]*c1[x2-x1+1]*c2[y2-y1+1]; 
}
ull get_hash3(int x1, int y1, int x2, int y2) {
    return f3[x2][y2] - f3[x1-1][y2]*c1[x2-x1+1] - f3[x2][y1-1]*c2[y2-y1+1] + f3[x1-1][y1-1]*c1[x2-x1+1]*c2[y2-y1+1]; 
}

我的写法有问题吗

2023/10/4 10:44
加载中...