Digital Library[ Search Result ]
An Improved Algorithm of Finding a Maximal Common Subsequence
Hyeonjun Shin, Joong Chae Na, Jeong Seop Sim
http://doi.org/10.5626/JOK.2023.50.9.737
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.
An Improved Algorithm for Finding a Longer Maximal Common Subsequence
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.
Search
Journal of KIISE
- ISSN : 2383-630X(Print)
- ISSN : 2383-6296(Electronic)
- KCI Accredited Journal
Editorial Office
- Tel. +82-2-588-9240
- Fax. +82-2-521-1352
- E-mail. chwoo@kiise.or.kr