首页    期刊浏览 2024年11月08日 星期五
登录注册

文章基本信息

  • 标题:Small Longest Tandem Scattered Subsequences
  • 本地全文:下载
  • 作者:Luıs M. S. Russo ; Alexandre P. Francisco
  • 期刊名称:Scientific Annals of Computer Science
  • 印刷版ISSN:1843-8121
  • 出版年度:2021
  • 卷号:XXXI
  • 期号:1
  • 页码:79-110
  • DOI:10.7561/SACS.2021.1.79
  • 语种:English
  • 出版社:Alexandru Ioan Cuza University of Iasi
  • 摘要:We consider the problem of identifying tandem scattered subsequences within a string. Our algorithm identifies a longest subsequence which occurs twice without overlap in a string. This algorithm is based on the Hunt-Szymanski algorithm, therefore its performance improves if the string is not self similar, which occurs naturally on strings over large alphabets. Our algorithm relies on new results for data structures that support dynamic longest increasing sub-sequences. In the process we also obtain improved algorithms for the decremental string comparison problem.
国家哲学社会科学文献中心版权所有