Efficient Representation and Parallel Computation of String-Substring Longest Common Subsequences.
Alexander Tiskin · Warwick Research Archive Portal (University of Warwick) · 2006
Given two strings a, b of length m, n respectively, the string-substring longest common subsequence (SS-LCS) problem consists in computing the length of the longest common subsequence of a and every substring of b. An explicit representation of the output lengths is of size o(n2). We show that the output can be represented implicitly by a set of n two-dimensional integer points, where individual output lengths are obtained by dominance counting queries.This leads to a data structure of size O(n), which allows to query an individual output length in time O( log n log log n), using a recent result by JaJa, Mortensen and Shi. The currently best sequential SS-LCS algorithm by Alves et al. can be adapted to produce the output in the above geometric representation. We also develop a new parallel SS-LCS algorithm that runs on a p-processor coarse-grained computer in O(mn/p ) local computation, O(n log p) communication,O(log p) barrier synchronisations, and O(n) memory per processor, producing the output in the above geometric representation. Compared to previously known results, our approach presents a substantial improvement in algorithm functionality, output representation efficiency, communication efficiency and/or memory efficiency