Name
Abstract | ||
|---|---|---|
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. |
Year | Venue | Field |
|---|---|---|
2018 | CPM | String searching algorithm,Discrete mathematics,Degenerate energy levels,Online algorithm,Combinatorics,Computer science,Working space,Elasticity (economics) |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kotaro Aoyama | 1 | 0 | 0.34 |
| Yuto Nakashima | 2 | 57 | 19.52 |
| Tomohiro I | 3 | 148 | 22.06 |
| Shunsuke Inenaga | 4 | 595 | 79.02 |
| Hideo Bannai | 5 | 620 | 79.87 |
| Masayuki Takeda | 6 | 9 | 13.78 |