Loading...
Please wait, while we are loading the content...
Similar Documents
Even Faster Elastic-Degenerate String Matching via Fast Matrix Multiplication
| Content Provider | Paperity |
|---|---|
| Author | Rosone, Giovanna Pisanti, Nadia Bernardini, Giulia Gawrychowski, Pawel Pissis, Solon P. |
| Abstract | An elastic-degenerate (ED) string is a sequence of n sets of strings of total length N, which was recently proposed to model a set of similar sequences. The ED string matching (EDSM) problem is to find all occurrences of a pattern of length m in an ED text. The EDSM problem has recently received some attention in the combinatorial pattern matching community, and an O(nm^{1.5}sqrt{log m} + N)-time algorithm is known [Aoyama et al., CPM 2018]. The standard assumption in the prior work on this question is that N is substantially larger than both n and m, and thus we would like to have a linear dependency on the former. Under this assumption, the natural open problem is whether we can decrease the 1.5 exponent in the time complexity, similarly as in the related (but, to the best of our knowledge, not equivalent) word break problem [Backurs and Indyk, FOCS 2016]. |
| Starting Page | 21:1 |
| Ending Page | 21:15 |
| File Format | HTM / HTML |
| DOI | 10.4230/LIPIcs.ICALP.2019.21 |
| Journal | Leibniz International Proceedings in Informatics |
| Volume Number | 132 |
| Language | English |
| Publisher | Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik |
| Publisher Date | 2019-07-08 |
| Access Restriction | Open |
| Subject Keyword | String algorithms Fast fourier transform Matrix multiplication Elastic-degenerate string Pattern matching |
| Content Type | Text |
| Resource Type | Article |
