We give an alphabet-independent optimal parallel algorithm for the searching phase of three-dimensional pattern-matching. All occurrences of a three dimensional pattern P of shape $m \times m \times m$ in a text T of shape $n \times n \times n$ are to be found. Our algorithm works in $\log m$ time with ${\mathcal O}(N/\log(m))$ processors of a {\em CREW PRAM}, where $N = n^3$. The ideas from [3] are used. Surprisingly, the extension of the two dimensional matching to the three dimensional one is not a trivial modification. The searching phase in three dimensions explores classification of two-dimensional periodicities of the cubic pattern. Some projection techniques are developed to deal with three dimensions. The periodicites of the patern with respect to its faces are investigated. The nonperiodicities imply some sparseness properties, while periodicities imply other special useful properties ({\it i.e.} monotonicity) of the set of occurrences. Both types of properties are useful in deriving an efficient algorithm.
The search phase is preceeded by the preprocessing phase (computation of the witness table). Our main results concern the searching phase, however we present shortly a new approach to the second phase also. Usefullness of the dictionaries of basic factors ({\it DBF}\/'s), see [7], in the computation of the three dimensional witness table is presented. The {\it DBF} approach gains simplicity at the expense of a small increase in time. It gives a (nonoptimal) ${\mathcal O}(\log(m))$ time algorithm using $m$ processors of a {\em CRCW PRAM}. The alphabet-independent optimal preprocessing is very complex even in the case of two dimensions, see [9]. For large alphabets the {\em DBF\/}'s give assymptotically the same complexity as the (alphabet-dependent) suffix trees approach (but avoids suffix trees and is simpler).
However the basic advantage of the {\em DBF} approach is simplicity of dealing with three (or more) dimensions.
The algorithm can be easily adjusted to the case of unequally sided patterns.