http://poj.org/problem?id=3690

计算出所有模式阵hash值,然后算所有文本子阵的哈希值,在模式阵中找,找到就从模式阵中删掉,最后输出删了多少个。
由于有相同的模式,若没在星空中出现则都要算,所以用multiset存。

/*719ms,9616KB*/

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 = 0;
        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 = 0;
        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;
        }
    }
}

multiset<ull> unseen; /// 由于有相同的模式,若没在星空中出现则都要算,所以用multiset

int main()
{
    int n, m, t, i, j, cas = 0;
    while (SIIIII(n, m, t, x, y), n)
    {
        Pcas();
        For(i, n) SS(s[i]);
        unseen.clear();
        For(j, t)
        {
            For(i, x) SS(p[i]);
            get_hash(p, x, y);
            unseen.insert(ha[0][0]);
        }
        get_hash(s, n, m);
        For(i, n - x + 1) For(j, m - y + 1) unseen.erase(ha[i][j]);
        PI(t - unseen.size());
    }
    return 0;
}

Comments

comments powered by Disqus