Shortest Unique Substring Queries on Run-Length Encoded Strings

DOI10.4230/LIPICS.MFCS.2016.69zbMATH Open1398.68109OpenAlexW2533951358MaRDI QIDQ4608632FDOQ4608632

Authors: Takuya Mieno, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda 

Publication date: 21 March 2018

Full work available at URL: http://dx.doi.org/10.4230/LIPIcs.MFCS.2016.69

Recommendations

• Shortest unique palindromic substring queries on run-length encoded strings
• Shortest unique substring query revisited
• Shortest unique substrings queries in optimal time
• Fast algorithms for the shortest unique palindromic substring problem on run-length encoded strings
• A simple yet time-optimal and linear-space algorithm for shortest unique substring queries
• Shortest unique palindromic substring queries in semi-dynamic settings
• Shortest unique palindromic substring queries in optimal time
• Tight bounds on the maximum number of shortest unique substrings

zbMATH Keywords

string algorithmsrun-length encodingshortest unique substring

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32)

Cited In (12)

• In-place algorithms for exact and approximate shortest unique substring problems
• Computing minimal unique substrings for a sliding window
• Algorithms and combinatorial properties on shortest unique palindromic substrings
• Fast algorithms for the shortest unique palindromic substring problem on run-length encoded strings
• Minimal Unique Substrings and Minimal Absent Words in a Sliding Window
• Shortest unique palindromic substring queries on run-length encoded strings
• Space-time trade-offs for finding shortest unique substrings and maximal unique matches
• Compact data structures for shortest unique substring queries
• Range shortest unique substring queries
• Shortest unique substring query revisited
• Tight bounds on the maximum number of shortest unique substrings
• Space-efficient algorithms for computing minimal/shortest unique substrings

This page was built for publication: Shortest Unique Substring Queries on Run-Length Encoded Strings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4608632)