Hyeonjun Shin  Joong Chae Na  Jeong Seop Sim

10.5626/JOK.2023.50.9.737

maximal common subsequences longest common subsequences string comparison string algorithms

A maximal common subsequence (MCS) of two strings is a common subsequence that cannot be extended by inserting any character. Unlike the longest common subsequence (LCS), the length of MCS can vary as the longest MCS is an LCS. Although LCS is commonly used to compare similarities of two sequences, computing can take a significant amount of time. Hence, finding a longer MCS is important, as it can be computed faster than the LCS. An algorithm was proposed to compute one of the MCSs of two strings X and Y of total length n using O(kn) space and O(n√(logn/loglogn)) time. Improved algorithms were also proposed. In this paper, we present an algorithm that can check for more characters to compute an MCS. The algorithm proposed in this paper runs in O(kn) space and O(n√(logn/loglogn)) time for a given constant k. Experimental results using both real and randomly generated data showed that the length of the MCS computed by the algorithm proposed in this paper could be up to 6.31 times longer than those computed by previous algorithms.