Document Open Access Logo

Maximal Common Subsequence Algorithms

Author Yoshifumi Sakai

PDF
Thumbnail PDF

File

LIPIcs.CPM.2018.1.pdf
  • Filesize: 434 kB
  • 10 pages

Document Identifiers

Author Details

Yoshifumi Sakai
  • Graduate School of Agricultural Science, Tohoku University, 468-1, Aza-Aoba, Aramaki, Aoba-ku, Sendai 980-0845, Japan

Cite As Get BibTex

Yoshifumi Sakai. Maximal Common Subsequence Algorithms. In 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 105, pp. 1:1-1:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.CPM.2018.1

Abstract

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Pattern matching
Keywords
  • algorithms
  • string comparison
  • longest common subsequence
  • constrained longest common subsequence

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. Tight hardness results for lcs and other sequence similarity measures. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pages 59-78. IEEE, 2015. Google Scholar
  2. Yi-Ching Chen and Kun-Mao Chao. On the generalized constrained longest common subsequence problems. Journal of Combinatorial Optimization, 21(3):383-392, 2011. Google Scholar
  3. Francis YL Chin, Alfredo De Santis, Anna Lisa Ferrara, NL Ho, and SK Kim. A simple algorithm for the constrained sequence problems. Information Processing Letters, 90(4):175-179, 2004. Google Scholar
  4. Campbell B Fraser, Robert W Irving, and Martin Middendorf. Maximal common subsequences and minimal common supersequences. Information and Computation, 124(2):145-153, 1996. Google Scholar
  5. Zvi Gotthilf, Danny Hermelin, Gad M Landau, and Moshe Lewenstein. Restricted LCS. In International Symposium on String Processing and Information Retrieval, pages 250-257. Springer, 2010. Google Scholar
  6. Daniel S Hirschberg. Algorithms for the longest common subsequence problem. Journal of the ACM (JACM), 24(4):664-675, 1977. Google Scholar
  7. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. Journal of Computer and System Sciences, 62(2):367-375, 2001. Google Scholar
  8. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. Google Scholar
  9. Yin-Te Tsai. The constrained longest common subsequence problem. Information Processing Letters, 88(4):173-176, 2003. Google Scholar
  10. Robert A Wagner and Michael J Fischer. The string-to-string correction problem. Journal of the ACM (JACM), 21(1):168-173, 1974. Google Scholar
  11. Dan E Willard. Log-logarithmic worst-case range queries are possible in space Θ(N). Information Processing Letters, 17(2):81-84, 1983. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact