Faster Longest Common Extension Queries in Strings over General Alphabets

DOI10.4230/LIPIcs.CPM.2016.5zbMath1380.68474arXiv1602.00447OpenAlexW2963452431MaRDI QIDQ5369537

Paweł Gawrychowski, Tomasz Kociumaka, Tomasz Walen, Wojciech Rytter

Publication date: 17 October 2017

Full work available at URL: https://arxiv.org/abs/1602.00447

zbMATH Keywords

longest common prefixdifference coverlongest common extensionmaximal repetitions

Mathematics Subject Classification ID

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

Related Items (11)

Tight lower bounds for the longest common extension problem ⋮ Computing longest common extensions in partial words ⋮ Absent Subsequences in Words ⋮ Near-optimal quantum algorithms for string problems ⋮ Optimal bounds for computing \({\alpha}\)-gapped repeats ⋮ Cartesian and Lyndon trees ⋮ Computing runs on a trie ⋮ On the size of overlapping Lempel-Ziv and Lyndon factorizations ⋮ On the size of the smallest alphabet for Lyndon trees ⋮ Small-space LCE data structure with constant-time queries ⋮ Almost linear time computation of maximal repetitions in run length encoded strings

This page was built for publication: Faster Longest Common Extension Queries in Strings over General Alphabets