Computing longest common square subsequences

Takafumi Inoue, Shunsuke Inenaga, Heikki Hyyrö, Hideo Bannai, Masayuki Takeda

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Citations (Scopus)


A square is a non-empty string of form Y Y. The longest common square subsequence (LCSqS) problem is to compute a longest square occurring as a subsequence in two given strings A and B. We show that the problem can easily be solved in O(n6) time or O(|M|n4) time with O(n4) space, where n is the length of the strings and M is the set of matching points between A and B. Then, we show that the problem can also be solved in O(σ|M|3 + n) time and O(|M|2 + n) space, or in O(|M|3 log2 n log log n + n) time with O(|M|3 + n) space, where σ is the number of distinct characters occurring in A and B. We also study lower bounds for the LCSqS problem for two or more strings.

Original languageEnglish
Title of host publication29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018
EditorsBinhai Zhu, Gonzalo Navarro, David Sankoff
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Number of pages1363
ISBN (Electronic)9783959770743
Publication statusPublished - May 1 2018
Event29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018 - Qingdao, China
Duration: Jul 2 2018Jul 4 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Other29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018

All Science Journal Classification (ASJC) codes

  • Software


Dive into the research topics of 'Computing longest common square subsequences'. Together they form a unique fingerprint.

Cite this