Efficient methods find repeated patterns in long texts faster
Output-Sensitive Enumeration of Maximal Closed Substrings in Linear Space
Data Structures and Algorithms
Summary
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.
What this means in practice
- •For text indexing engineers: Implement faster substring search tools that find unique repeated segments with less memory, improving text database indexing.
- •For bioinformatics software developers: Enhance DNA sequence analysis by efficiently detecting repeated genetic patterns using less computational resources.
Authors
Johannes Fischer, Dominik Köppl
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.