A data structure for substring-substring LCS length queries

研究成果: Article査読

1 被引用数 (Scopus)


The longest common subsequence (LCS) length of two strings is used as one of the most fundamental metrics measuring the similarity between the strings. To find out the local structures common to the strings under this similarity metric, we need a fast calculation of the LCS length of any pair of substrings of the two strings. For supporting such queries, it makes sense to preprocess the two strings in a quadratic time, because it takes about the same amount of time to compute the LCS length of the entire strings from scratch. We propose a quadratic-time constructible data structure that supports sublinear-time queries of the LCS length for any pair of substrings. The query time is O(llog1+ϵ⁡l), where ϵ is a positive constant arbitrarily small and l is the sum of the substring lengths.

ジャーナルTheoretical Computer Science
出版ステータスPublished - 2022 4月 8

ASJC Scopus subject areas

  • 理論的コンピュータサイエンス
  • コンピュータ サイエンス(全般)


「A data structure for substring-substring LCS length queries」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。