A coarse-grained parallel algorithm for the all-substrings longest common subsequence problem

Given two strings A and B of lengths n(a) and n(b), respectively, the All-substrings Longest Common Subsequence (ALCS) problem obtains, for any substring B' of B, the length of the longest string that is a subsequence of both A and B'. The sequential algorithm for this problem takes O(n(a)n(b)) time and O(n(b)) space. We present a parallel algorithm for the ALCS problem on the Coarse-Grained Multicomputer (BSP/CGM) model with p < root n(a) processors, that takes O(n(a)n(b)/p) time, O(log p) communication rounds and O(n(b)root n(a)) space per processor. The proposed algorithm also solves the basic Longest Common Subsequence (LCS) problem that finds the longest string ( and not only its length) that is a subsequence of both A and B. To our knowledge, this is the best BSP/CGM algorithm in the literature for the LCS and ALCS problems.