What question did this study set out to answer?

This research aims to improve the computation of shortest unique and absent substrings in strings with small alphabets.

June 10, 2026Open Access

Faster Algorithms for Shortest Unique or Absent Substrings

Key Points

This research aims to improve the computation of shortest unique and absent substrings in strings with small alphabets.
Developed an 𝒪(n log σ/√{log n})-time algorithm for shortest unique substring computation.
Decomposed the problem based on length and period of substrings using various analytical techniques.
Combined the unique substring algorithm with efficient de Bruijn sequence construction for absent substring.
Achieved a significant reduction in computational time for both problems compared to folklore solutions.
Provided a new geometric approach for substring computation that enhances performance.
Demonstrated efficiencies particularly for small alphabets in the word RAM model.

Abstract

We revisit two well-known algorithmic problems on strings: computing a shortest unique substring (SUS) and a shortest absent substring (SAS) in a string S of length n. Both problems admit folklore 𝒪 (n) -time solutions using the suffix tree of S. However, for small alphabets, this complexity is not necessarily optimal in the word RAM model, where a string of length n over alphabet [0, σ) can be stored in 𝒪 (n log σ/log n) space and read in 𝒪 (n log σ/log n) time. We present an 𝒪 (n log σ/√log n) -time algorithm for computing a SUS in S. This algorithm decomposes the problem according to the length and the period of the sought substring and uses several tools and techniques, such as synchronizing sets, the analysis of runs, and wavelet trees, to reduce the computation of a SUS to a simple geometric problem. Further, we adapt this algorithm and combine it with an efficient construction of de Bruijn sequences in order to obtain an 𝒪 (n log σ/√log n) -time algorithm for computing a SAS in S.

KI fragen

Bookmark

View Full Paper