Longest Square Subsequence Problem Revisited

Takafumi Inoue, Shunsuke Inenaga, Hideo Bannai

研究成果: 書籍/レポート タイプへの寄稿会議への寄与

2 被引用数 (Scopus)

抄録

The longest square subsequence (LSS) problem consists of computing a longest subsequence of a given string S that is a square, i.e., a longest subsequence of form XX appearing in S. It is known that an LSS of a string S of length n can be computed using time [Kosowski 2004], or with (model-dependent) polylogarithmic speed-ups using time [Tiskin 2013]. We present the first algorithm for LSS whose running time depends on other parameters, i.e., we show that an LSS of S can be computed in time with O(M) space, where r is the length of an LSS of S and M is the number of matching points on S.

本文言語英語
ホスト出版物のタイトルString Processing and Information Retrieval - 27th International Symposium, SPIRE 2020, Proceedings
編集者Christina Boucher, Sharma V. Thankachan
出版社Springer Science and Business Media Deutschland GmbH
ページ147-154
ページ数8
ISBN(印刷版)9783030592110
DOI
出版ステータス出版済み - 2020
イベント27th International Symposium on String Processing and Information Retrieval, SPIRE 2020 - Orlando, 米国
継続期間: 10月 13 202010月 15 2020

出版物シリーズ

名前Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
12303 LNCS
ISSN(印刷版)0302-9743
ISSN(電子版)1611-3349

会議

会議27th International Symposium on String Processing and Information Retrieval, SPIRE 2020
国/地域米国
CityOrlando
Period10/13/2010/15/20

!!!All Science Journal Classification (ASJC) codes

  • 理論的コンピュータサイエンス
  • コンピュータサイエンス一般

フィンガープリント

「Longest Square Subsequence Problem Revisited」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。

引用スタイル