2020/04/11 by Kazuya Tsuruta, Dominik Köppl, Tsuruta, Kazuya +9
Computer Science · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Natural Language Processing Techniques #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2004.05309
openalex publication_date 2020/04/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We introduce a new class of straight-line programs (SLPs), named the Lyndon SLP, inspired by the Lyndon trees (Barcelo, 1990). Based on this SLP, we propose a self-index data structure of O(g) words of space that can be built from a string T in O(n \lg n) expected time, retrieving the starting positions of all occurrences of a pattern P of length m in O(m + \lg m \lg n + occ \lg g) time, where n is the length of T, g is the size of the Lyndon SLP for T, and occ is the number of occurrences of P in T.