A BSP/CGM algorithm for the all-substrings longest common subsequence problem

Given two strings X and Y of lengths m and n, re-spectively, the all-substrings longest common subsequence (ALCS) problem obtains the lengths of the subsequences common to X and any substring of Y. The sequential al-gorithm takes O(mn) time and O(n) space. We present a parallel algorithm for ALCS on a coarse-grained multi-computer (BSP/CGM) model with p < pm processors that takes O(mn=p) time and O(n p m) space per processor, with O(log p) communication rounds. The proposed paral-lel algorithm also solves the well-known LCS problem. To our knowledge this is the best BSP/CGM algorithm for the ALCS problem in the literature. 1