AOJ 1312 Where‘s Wally（哈希）

Do you know the famous series of children’s books named “Where’s Wally”? Each of the books contains a variety of pictures of hundreds of people. Readers are challenged to find a person called Wally in the crowd.
We can consider “Where’s Wally” as a kind of pattern matching of two-dimensional graphical images. Wally’s figure is to be looked for in the picture. It would be interesting to write a computer program to solve “Where’s Wally”, but this is not an easy task since Wally in the pictures may be slightly different in his appearances. We give up the idea, and make the problem much easier to solve. You are requested to solve an easier version of the graphical pattern matching problem.
An image and a pattern are given. Both are rectangular matrices of bits (in fact, the pattern is always square-shaped). 0 means white, and 1 black. The problem here is to count the number of occurrences of the pattern in the image, i.e. the number of squares in the image exactly matching the pattern. Patterns appearing rotated by any multiples of 90 degrees and/or turned over forming a mirror image should also be taken into account.
Input
The input is a sequence of datasets each in the following format.
w h p
image data
pattern data

The first line of a dataset consists of three positive integers w, h and p. w is the width of the image and h is the height of the image. Both are counted in numbers of bits. p is the width and height of the pattern. The pattern is always square-shaped. You may assume 1 ≤ w ≤ 1000, 1 ≤ h ≤ 1000, and 1 ≤ p ≤ 100.
The following h lines give the image. Each line consists of ⌈w/6⌉ (which is equal to &⌊(w+5)/6⌋) characters, and corresponds to a horizontal line of the image. Each of these characters represents six bits on the image line, from left to right, in a variant of the BASE64 encoding format. The encoding rule is given in the following table. The most significant bit of the value in the table corresponds to the leftmost bit in the image. The last character may also represent a few bits beyond the width of the image; these bits should be ignored.

character value (six bits)

原来的字母	对应的数字
A - Z	0 - 25
a - z	26 - 51
0 - 9	52 - 61
+	62
/	61

The last p lines give the pattern. Each line consists of ⌈p/6⌉ characters, and is encoded in the same way as the image.
A line containing three zeros indicates the end of the input. The total size of the input does not exceed two megabytes.
Output
For each dataset in the input, one line containing the number of matched squares in the image should be output. An output line should not contain extra characters.
Two or more matching squares may be mutually overlapping. In such a case, they are counted separately. On the other hand, a single square is never counted twice or more, even if it matches both the original pattern and its rotation, for example.

Sample Input
48 3 3
gAY4I4wA
gIIgIIgg
w4IAYAg4
g
g
w
153 3 3
kkkkkkkkkkkkkkkkkkkkkkkkkg
SSSSSSSSSSSSSSSSSSSSSSSSSQ
JJJJJJJJJJJJJJJJJJJJJJJJJI
g
Q
I
1 1 2
A
A
A
384 3 2
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/
BCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/A
CDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/AB
A
A
0 0 0

Output for the Sample Input
8
51
0
98

题意：
输入三个数w, h, p
h行w列个数字，把它按照上面的表格转换为二进制数。多了就删掉
得到field
例如第二个案例
//三行应该是对齐的，但是scdn它大小写字母所占位置大小不一
153 3 3
kkkkkkkkkkkkkkkkkkkkkkkkkg
SSSSSSSSSSSSSSSSSSSSSSSSSQ
JJJJJJJJJJJJJJJJJJJJJJJJJI
g
Q
I
每行有（153 + 5）/ 6 = 26个字母，但是最后还是只有153个二进制

输入p个字母，截取前面 p/6 个二进制数字，组成正方形G

问：
正方形G，旋转、翻转得到的8个正方形，在field中，可以找到共几个一样的

题解：
重点是把题意弄懂，然后用 哈希做

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<vector>
#include<cstdio>
#include<set>
#define ll long long
#define ull unsigned long long
using namespace std;
int N, M, P, Q;
const int MAX = 6e3 + 10;
char scan[MAX][MAX];
char field[MAX][MAX];
char G[660][660];
char patterns[8][MAX][MAX];
ull hash[MAX][MAX], temp[MAX][MAX];

void compute_hash(char a[MAX][MAX], int n, int m) {
    const ull B1 = 1e9 - 7;
    const ull B2 = 1e9 + 7;
    ull t1 = 1;
    for(int j = 0; j < Q; j++) t1 *= B1;

    for(int i = 0; i < n; i++) {
        ull e = 0;
        for(int j = 0; j < Q; j++) e = e * B1 + a[i][j];

        for(int j = 0; j + Q <= m; j++) {
            temp[i][j] = e;
            if(j + Q < m) e = e * B1 + a[i][j + Q] - a[i][j] * t1;
        }
    }

    ull t2 = 1;
    for(int i = 0; i < P; i++) t2 *= B2;

    for(int j = 0; j + Q <= m; j++) {
        ull e = 0;
        for(int i = 0; i < P; i++) e = e * B2 + temp[i][j];

        for(int i = 0; i + P <= n; i++) {
            hash[i][j] = e;
            if(i + P < n) e = e * B2 + temp[i + P][j] - temp[i][j] * t2;
        }
    }
}

int getnum(char x) {
    if(x >= 'A' && x <= 'Z') return x - 'A';
    else if(x >= 'a' && x <= 'z') return x - 'a' + 26;
    else if(x >= '0' && x <= '9') return x - '0' + 52;
    else if(x == '+') return 62;
    else return 63;
}

int main() {
    int w, h, p;
    while(cin >> w >> h >> p && w, h, p) {
        memset(scan, 0, sizeof(scan));
        memset(field, 0, sizeof(field));
        memset(G, 0, sizeof(G));
        M = w; N = h;P = Q = p;
        for(int i = 0; i < h; i++)
            cin >> scan[i];

        //将输入的编码转换为二进制 eg. g -> 100 000
        for(int i = 0; i < h; i++) {
            int cnt = 0;
            for(int j = 0; j < (w + 5) / 6; j++) {
                int x = getnum(scan[i][j]);
                int k = 5;
                while(k >= 0) {
                    field[i][cnt] = ((x >> k) & 1) + '0';
                    k--;
                    cnt++;
                }
            }
        }

        //将输入的编码转换为二进制,二进制只取前面的 p/6个
        for(int i = 0; i < p; i++) {
            int cnt = 0;
            for(int j = 0; j < (p + 5) / 6; j++) {
                char c;
                cin >> c;
                int x = getnum(c);
                int k = 5;
                while(k >= 0) {
                    G[i][cnt] = ((x >> k) & 1) + '0';
                    k--;
                    cnt++;
                }
            }
        }

        //在pattern上储存翻转、旋转的8种
        //前两个
        for(int i = 0; i < p; i++) {
            for(int j = 0; j < p; j++) {
                patterns[0][i][j] = G[i][j];
                patterns[1][i][j] = G[i][p - j - 1];
            }
        }
        for(int k = 2; k <= 6; k += 2) {
            for(int i = 0; i < p; i++) {
                for(int j = 0; j < p; j++) {
                    //分别逆时针旋转90度 翻转前的 和 翻转后的
                    patterns[k][j][i] = patterns[k - 2][i][p - j - 1];
                    patterns[k + 1][j][i] = patterns[k - 1][i][p - j - 1];
                }
            }
        }

        set<ll>unseen;
        for(int k = 0; k < 8; k++) {
            compute_hash(patterns[k], p, p);
            unseen.insert(hash[0][0]);
        }
        compute_hash(field, N, M);

        int ans = 0;
        for(int i = 0; i + p <= N; i++) {
            for(int j = 0; j + p <= M; j++)
                if(unseen.find(hash[i][j]) != unseen.end())
                    ans++;
        }
        cout << ans << endl;
    }
}