TY - GEN
T1 - Maximal common subsequence algorithms
AU - Sakai, Yoshifumi
N1 - Publisher Copyright:
© 2018 Yoshifumi Sakai; licensed under Creative Commons License CC-BY.
PY - 2018/5/1
Y1 - 2018/5/1
N2 - A common subsequence of two strings is maximal, if inserting any character into the subsequence can no longer yield a common subsequence of the two strings. The present article proposes a (sub)linearithmic-time, linear-space algorithm for finding a maximal common subsequence of two strings and also proposes a linear-time algorithm for determining if a common subsequence of two strings is maximal.
AB - A common subsequence of two strings is maximal, if inserting any character into the subsequence can no longer yield a common subsequence of the two strings. The present article proposes a (sub)linearithmic-time, linear-space algorithm for finding a maximal common subsequence of two strings and also proposes a linear-time algorithm for determining if a common subsequence of two strings is maximal.
KW - Algorithms
KW - Constrained longest common subsequence
KW - Longest common subsequence
KW - String comparison
UR - http://www.scopus.com/inward/record.url?scp=85048249938&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85048249938&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.CPM.2018.1
DO - 10.4230/LIPIcs.CPM.2018.1
M3 - Conference contribution
AN - SCOPUS:85048249938
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 11
EP - 110
BT - 29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018
A2 - Zhu, Binhai
A2 - Navarro, Gonzalo
A2 - Sankoff, David
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018
Y2 - 2 July 2018 through 4 July 2018
ER -