String processing on the hypercube

Parallel algorithms are given for solving some string-comparison problems on the hypercube. These algorithms are widely applicable to the problems of speech and signal processing. For strings x and y with length (x)=m, length (y)=n, and assuming n⩾m, the authors show that the substring problem can be solved in O(m+log(n/m)) time using O( m) space per processing element (PE) on an MIMD hypercube of O(n/m) PEs. They note that this algorithm has an optimal processor-time product if m is bounded below by log( n/m). The results of implementing this algorithm on the NCUBE/7 hypercube machine are presented. The authors also show that the longest common substring problem can be solved in O(log n) time using O(1) space per PE on an SIMD hypercube of O(n²) PEs. It is shown that the string edit problem, the longest common subsequence problem, the minimum-length time-warping problem, and many other speech recognition problems can be solved in O(log²n) time using O(1) space per PE on an SIMD hypercube of O(n³/log²n) PEs