The longest common subsequence (LCS) problem is a classical method of string comparison. Several coarse-grained parallel algorithms for the LCS problem have been proposed in the past. However, none of these algorithms achieve scalable communication. In this paper, we propose the first coarse-grained parallel LCS algorithm with scalable communication. Moreover, the algorithm is work-optimal, synchronisation-efficient, and solves a more general problem of semi-local string comparison, improving in at least two of these aspects on each of the predecessors. © 2008 The authors and IOS Press. All rights reserved.