http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1960

注意利用一点点技巧,可以只开一个hash数组。

/*0.165s*/

const int mx = 1005;
const ull B1 = 9973ULL;
const ull B2 = ull(1e8) + 7;

char s[mx][mx], p[mx][mx];
ull ha[mx][mx];
int x, y;

void get_hash(char a[mx][mx], int n, int m)
{
    ull t = 1ULL, e, tmp;
    int i, j;
    For(j, y) t *= B1;
    For(i, n)
    {
        e = 0ULL;
        For(j, y) e = e * B1 + a[i][j];
        For(j, m - y + 1)
        {
            ha[i][j] = e;
            if (j < m - y) e = e * B1 - t * a[i][j] + a[i][j + y];
        }
    }
    t = 1ULL;
    For(i, x) t *= B2;
    For(j, m - y + 1)
    {
        e = 0ULL;
        For(i, x) e = e * B2 + ha[i][j];
        For(i, n - x + 1)
        {
            tmp = e; /// 循环数组的技巧
         if (i < n - x) e = e * B2 - t * ha[i][j] + ha[i + x][j];
            ha[i][j] = tmp;
        }
    }
}

int main()
{
    int t, n, m, i, j, ans;
    ull h;
    SI(t);
    while (t--)
    {
        SII(n, m);
        For(i, n) SS(s[i]);
        SII(x, y);
        For(i, x) SS(p[i]);
        get_hash(p, x, y);
        h = ha[0][0];
        get_hash(s, n, m);
        ans = 0;
        For(i, n - x + 1) For(j, m - y + 1) if (ha[i][j] == h) ++ans;
        PI(ans);
    }
    return 0;
}

Comments

comments powered by Disqus