An Improved Algorithm for Finding a Longer Maximal Common Subsequence

DongYeop Lee, Joong Chae Na

http://doi.org/10.5626/JOK.2022.49.7.507

A maximal common subsequence (MCS) is a common subsequence which is not common any more if any character is inserted into it. Recently, a (sub)linearithmic-time algorithm for finding an MCS of two strings has been proposed. The MCS algorithm is faster than algorithms for computing the longest common subsequence (LCS), which requires quadratic time. However, it has been shown experimentally that the MCS computed by the existing algorithm is much shorter than the LCS. In this paper, we propose two algorithms for computing a longer MCS by improving the existing algorithm and show experimental results of various real data and randomly generated data. Our algorithms compute MCSs whose lengths are 1.47 to 3.17 times for real data and 1.50 to 3.08 times for random data, compared to the lengths of MCSs computed by the existing algorithm.