Faster Online Elastic Degenerate String Matching
Faster Online Elastic Degenerate String Matching
复制标题
DOI：
10.4230/lipics.cpm.2018.9
复制
发表时间：
2018-05
期刊：
影响因子：
--
通讯作者：
Kotaro Aoyama;Yuto Nakashima;I. Tomohiro;Shunsuke Inenaga;H. Bannai;M. Takeda
中科院分区：
文献类型：
--
作者：
Kotaro Aoyama;Yuto Nakashima;I. Tomohiro;Shunsuke Inenaga;H. Bannai;M. Takeda
弹性简并字符串[Iliopoulus et al.， LATA 2017]是字符串集合的序列，最近被提出作为一种建模一组相似序列的方法。给出了一种求解弹性-退化字符串匹配（EDSM）问题的在线算法，该算法运行时间为O(nm sqrt{m log m} + N)，工作空间为O(m)，其中N为文本中弹性退化段的个数，N为文本中所有字符串的总长度，m为模式的长度。这改进了Grossi等人[CPM 2017]之前的算法，该算法运行时间为O（nm^2 + N）。
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.