Computing a longest common subsequence for a set of strings

The known 2-string LCS problem is generalized to finding a Longest Common Subsequence (LCS) for a set of strings. A new, general approach that systematically enumerates common subsequences is proposed for the solution. Assuming a finite symbol set, it is shown that the presented scheme requires a preprocessing time that grows linearly with the total length of the input strings and a processing time that grows linearly with (K), the number of strings, and () the number of matches among them. The only previous algorithm for the generalized LCS problem takesO(K·|S₁|·|S₂|·...|S_k|) execution time, where |S_i| denotes the length of the stringS_i. Since typically is a very small percentage of |S₁|·|S₂|·...·|S_k|, the proposed method may be considered to be much more efficient than the straightforward dynamic programming approach.