Given two or more strings (for example,DNA and amino acid sequences),the
longest common subsequence(LCS)problem is to determine the longest common
subsequence obtained by deleting zero or more symbols from each string. The
algorithms for computing an LCS between two strings were given by many papers,
but there is no efficient algorithm for computing an LCS between more than
two strings. This paper proposes a method for computing efficiently the LCS
between three or more strings of small alphabet size. Specifically, our
algorithm computes the LCS of $d$($\ge$ 3)strings of length $n$ on alphabet of
size $s$ in $O(nsd+Dsd(\log^{d-3}n+\log^{d-2}s))$ time, where $D$ is the number
of dominant matches and is much smaller than $n^d$. Through computational
experiments, we demonstrate the effectiveness of our algorithm.