TY  - JOUR
T1  - An Improved Algorithm for Finding a Longer Maximal Common Subsequence
AU  - Lee, DongYeop 
AU  - Na, Joong Chae 
JO  - Journal of KIISE, JOK
PY  - 2022
DA  - 2022/1/14
DO  - 10.5626/JOK.2022.49.7.507
KW  - maximal common subsequences
KW  - longest common subsequences
KW  - string comparison
KW  - string algorithms
AB  - 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.