Papers for

text indexing engineers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Efficient methods find repeated patterns in long texts faster

Output-Sensitive Enumeration of Maximal Closed Substrings in Linear Space

Abstract: We revisit the output-sensitive enumeration of maximal closed substrings (MCSs). Given a string of length $n$ over an integer alphabet, let $k$ 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 $\varepsilon>0$, we can report all MCSs in $O(n\sqrt{\log n}+k\log^\varepsilon n)$ time using $O(n)$ words of space, or in $O(n\sqrt{\log n}+k\log\log n)$ time using $O(n\log\log n)$ words. Both bounds include preprocessing and report occurrences by their endpoints. In particular, these algorithms improve the known $O(n\log n)$ worst-case time bound for sufficiently small output.

Wed 28 OctData Structures and Algorithms

The gist

Finding repeating parts in long strings can be slow, especially when many repeats are present. The authors improve this by using a new way to scan the string and quickly find all the largest repeated parts without extra pieces inside. Their approach works faster than earlier methods when there aren’t too many repeats and uses little computer memory. This means it can find these special repeats in long texts more efficiently.

Open → 2610.38114v1