Multi-dimensional pattern matching with dimensional wildcards

We introduce a new multi-dimensional pattern matching problem, which is a natural generalization of the on-line search in string matching. We are given a text matrix A[1: n(1), ..., 1:n(d)] of size N = n(1) x n(2) x ... x n(d), which we may preprocess. Then, we are given, on-line, an r-dimensional pattern matrix B[1: m(1), ..., 1:m(r)] of size M = m(1) x m(2) x ... x m(r), with 1 less than or equal to r less than or equal to d. We would like to know whether B* = B*[*, 1:m(1), *, ..., 1:m(r), *] occurs in A, where * is a dimensional wildcard such that B* is any d-dimensional matrix having size 1 x ... x m(1) x ... 1 x m(r) x ... 1 and containing the same elements as B. Notice that there might be ((r) (d)) less than or equal to 2(d) occurrences of B* for each position of A. We give CRCW-PRAM algorithms for preprocessing A in O(d log N) time with N-2/n(max) processors, where n(max) = max{n(1), ..., n(d)}. The on-line search for B* can be done in O(d log M) time and optimal O(dM) work.