程序竞赛中的字符串

/*==================================================*\ 
 | 字符串Hash 
 | 注意：mod选择足够大的质数（至少大于字符串个数） 
\*==================================================*/ 
unsigned int hasha(char *url, int mod) {
    unsigned int n = 0;
    char *b = (char *) &n;
    for (int i = 0; url[i]; ++i) b[i % 4] ^= url[i];
    return n % mod;
}

unsigned int hashb(char *url, int mod) {
    unsigned int h = 0, g;
    while (*url) {
        h = (h << 4) + *url++;
        g = h & 0xF0000000;
        if (g) h ^= g >> 24;
        h &= ~g;
    }
    return h % mod;
}

int hashc(char *p, int prime = 25013) {
    unsigned int h = 0, g;
    for (; *p; ++p) {
        h = (h << 4) + *p;
        if (g = h & 0xf0000000) {
            h = h ^ (g >> 24);
            h = h ^ g;
        }
    }
    return h % prime;
} 

/*==================================================*\ 
 | KMP匹配算法O(M+N) 
 | CALL: res=kmp(str, pat); 原串为str; 模式为pat(长为P); 
\*==================================================*/ 
int fail[P];

int kmp(char *str, char *pat) {
    int i, j, k;
    memset(fail, -1, sizeof(fail));
    for (i = 1; pat[i]; ++i) {
        for (k = fail[i - 1]; k >= 0 && pat[i] != pat[k + 1]; k = fail[k]);
        if (pat[k + 1] == pat[i]) fail[i] = k + 1;
    }
    i = j = 0;
    while (str[i] && pat[j]) { // By Fandywang  
        if (pat[j] == str[i]) ++i, ++j;
        else if (j == 0)++i;   //第一个字符匹配失败，从str下个字符开始  
        else j = fail[j - 1] + 1;
    }
    if (pat[j]) return -1; else return i - j;
} 

/*==================================================*\ 
 | Karp-Rabin字符串匹配 
 | hash(w[0..m-1]) = 
 | (w[0] * 2^(m-1) + ... + w[m-1] * 2^0) % q; 
 | hash(w[j+1..j+m]) = 
 | rehash(y[j], y[j+m], hash(w[j..j+m-1]); 
 | rehash(a, b, h) = ((h - a * 2^(m-1) ) * 2 + b) % q; 
 | 可以用q = 2^32简化%运算 
\*==================================================*/ 
#define REHASH(a, b, h) ((((h) - (a)*d) << 1) + (b))

int krmatch(char *x, int m, char *y, int n) { // search x in y  
    int d, hx, hy, i, j;
    for (d = i = 1; i < m; ++i) d = (d << 1);
    for (hy = hx = i = 0; i < m; ++i) {
        hx = ((hx << 1) + x[i]);
        hy = ((hy << 1) + y[i]);
    }
    for (j = 0; j <= n - m; ++j) {
        if (hx == hy && memcmp(x, y + j, m) == 0) return j;
        hy = REHASH(y[j], y[j + m], hy);
    }
} 

/*==================================================*\ 
 | 基于Karp-Rabin的字符块匹配 
 | Text: n * m matrix;  Pattern: x * y matrix; 
\*==================================================*/ 
#define uint unsigned int
const int A = 1024, B = 128;
const uint E = 27;
char text[A][A], patt[B][B];
uint ht, hp, pw[B * B], hor[A], ver[A][A];
int n, m, x, y;

void init() {
    int i, j = B * B;
    for (i = 1, pw[0] = 1; i < j; ++i) pw[i] = pw[i - 1] * E;
}

void hash() {
    int i, j;
    for (i = 0; i < n; ++i)
        for (j = 0, hor[i] = 0; j < y; ++j) {
            hor[i] *= pw[x];
            hor[i] += text[i][j] - 'a';
        }
    for (j = 0; j < m; ++j) {
        for (i = 0, ver[0][j] = 0; i < x; ++i) {
            ver[0][j] *= E;
            ver[0][j] += text[i][j] - 'a';
        }
        for (i = 1; i <= n - x; ++i)
            ver[i][j] = (ver[i - 1][j] - (text[i - 1][j] - 'a') * pw[x - 1]) * E + text[i + x - 1][j] - 'a';
    }
    for (j = 0, ht = hp = 0; j < y; ++j)
        for (i = 0; i < x; ++i) {
            ht *= E;
            ht += text[i][j] - 'a';
            hp *= E;
            hp += patt[i][j] - 'a';
        }
}

void read() {
    int i;
    scanf("%d%d", &n, &m);
    for (i = 0; i < n; ++i) scanf("%s", text[i]);
    scanf("%d%d", &x, &y);
    for (i = 0; i < x; ++i) scanf("%s", patt[i]);
}

int solve() {
    if (n == 0 || m == 0 || x == 0 || y == 0) return 0;
    int i, j, cnt = 0;
    uint t;
    for (i = 0; i <= n - x; ++i) {
        for (j = 0, t = ht; j <= m - y; ++j) {
            if (t == hp) ++cnt;
            t = (t - ver[i][j] * pw[y * x - x]) * pw[x] + ver[i][j + y];
        }
        ht = (ht - hor[i] * pw[x - 1]) * E + hor[i + x];
    }
    return cnt;
}

int main(void) {
    int T;
    init();
    for (scanf("%d", &T); T; --T) {
        read();
        hash();
        printf("%d\n", solve());
    }
    return 0;
}