pipette
ESEspañol

Output-Sensitive Enumeration of Maximal Closed Substrings in Linear Space

Johannes Fischer, Dominik K\"oppl

Preprint

In the authors' words

We revisit the output-sensitive enumeration of maximal closed substrings (MCSs). Given a string of length over an integer alphabet, let denote its number of MCS occurrences. We combine a right-to-left sweep on the string with range-successor queries to obtain all MCSs with two deterministic word-RAM bounds: for any fixed , we can report all MCSs in time using words of space, or in time using words. Both bounds include preprocessing and report occurrences by their endpoints. In particular, these algorithms improve the known worst-case time bound for sufficiently small output.

Main resultThe abstract does not state a limitation.

Appeared: Friday, October 30. arXiv. Preprint, not yet peer-reviewed.