DongYeop Lee  Joong Chae Na

10.5626/JOK.2022.49.7.507

maximal common subsequences longest common subsequences string comparison string algorithms

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.