Computing minimal unique substrings for a sliding window

DOI10.1007/s00453-021-00864-1OpenAlexW3195757721MaRDI QIDQ2118202

Hideo Bannai, Shunsuke Inenaga, Yuto Nakashima, Yuta Fujishige, Takuya Mieno, Masayuki Takeda

Publication date: 22 March 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-021-00864-1

zbMATH Keywords

sliding windowsuffix treeminimal unique substring

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items

Shortest unique palindromic substring queries in semi-dynamic settings, Data structures for computing unique palindromes in static and non-static strings

Cites Work

• String processing and information retrieval. 21st international symposium, SPIRE 2014, Ouro Preto, Brazil, October 20--22, 2014. Proceedings
• A simple yet time-optimal and linear-space algorithm for shortest unique substring queries
• Words and forbidden factors
• On-line construction of suffix trees
• Absent words in a sliding window with applications
• In-place algorithms for exact and approximate shortest unique substring problems
• Space-time trade-offs for finding shortest unique substrings and maximal unique matches
• Shortest Unique Substrings Queries in Optimal Time
• Minimum Unique Substrings and Maximum Repeats
• Minimal Unique Substrings and Minimal Absent Words in a Sliding Window
• A universal algorithm for sequential data compression
• Shortest Unique Substring Queries on Run-Length Encoded Strings