Application-specific array processors for the longest common subsequence problem of three sequences. - Luce, Guillaume (Parallel algorithms and applications.)
We design linear time systolic-based parallel algorithms that run on two-dimensional arrays for both computing the length and recovering a longest common subsequence of three given sequences that are appropriate for very large-scale integration (VLSI) implementation. These problems have been qualified to be difficult to be solved in linear time in [14], and our approach, which generalizes the methods used for determining a longest common subsequence of two strings [28, 38] to the case of three strings, enables to solve both problems in linear time. Given the three sequences A, B and C of length n, m and l (n < m < l), we provide an algorithm that computes the length p of their longest common subsequence on a modular I/O bounded one-way two-dimensional array of nm processors in n + 2m + 1 - 1 time steps. To compute a longest common subsequence of the three given strings, we show that each processor of the above array requires an O (min {n,p}) local storage to solve the problem in 2n+3m+l+p-2 time-steps.