Three-dimensional pattern matching
Zvi Galil, Jong Geun Park, Kunsoo Park · 1997
We present a parallel algorithm on a CRCW PRAM for three-dimensional pattern matching, i.e., finding all occurrences of a pattern of size TTZ3 in a text of size n3.The text search of the algorithm is alphabet-independent and runs in optimal constant time.The preprocessing computes a witness array for the pattern, and it runs in O(log m) time using rn3 processors.The witness computation uses multilayer suf%x trees and it works for any dimensions.Our result is based on a new characterization of three-dimensional periodicity.The parallel algorithm can be translated into a sequential algorithm for three-dimensional pattern match-ing whose text search is alphabet-independent and runs in 0(n3 ) time and whose preprocessing runs in 0(m3 log a) time, where u = min(l Xl, m3) and X is the alphabet of symbols.