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

文章基本信息

  • 标题:Faster Online Elastic Degenerate String Matching
  • 作者:Kotaro Aoyama ; Yuto Nakashima ; Tomohiro I
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2018
  • 卷号:105
  • 页码:9:1-9:10
  • DOI:10.4230/LIPIcs.CPM.2018.9
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:An Elastic-Degenerate String [Iliopoulus et al., LATA 2017] is a sequence of sets of strings, which was recently proposed as a way to model a set of similar sequences. We give an online algorithm for the Elastic-Degenerate String Matching (EDSM) problem that runs in O(nm sqrt{m log m} + N) time and O(m) working space, where n is the number of elastic degenerate segments of the text, N is the total length of all strings in the text, and m is the length of the pattern. This improves the previous algorithm by Grossi et al. [CPM 2017] that runs in O(nm^2 + N) time.
  • 关键词:elastic degenerate pattern matching; boolean convolution
Loading...
联系我们|关于我们|网站声明
国家哲学社会科学文献中心版权所有