Hypercube algorithms for some string comparison problems

Parallel algorithms are presented for solving some string-comparison problems on the hypercube. For strings x and y with length(x) = m, length(y) = n, and assuming n ≥ m, it is shown that the string-edit problem, the longest common subsequence problem, and the minimum-length time-warping problem can be solved in O(log²n) time using O(1) space per processing element (PE) on an SIMD hypercube of O(n³/log²n) PEs. It is also shown 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, and that the substring problem (where typically m is much smaller than n) can be solved in O(m + log n) time using O(m) space per PE on an MIMD hypercube of O(n/m) PEs; this algorithm has an optimal processor-time product if m = Ω(log n). The results of implementing this algorithm on the NCUBE/7 hypercube machine are presented.