Longest Lyndon Substring After Edit

DOI10.4230/LIPICS.CPM.2018.19MaRDI QIDQ5140783zbMATH OpenOpenAlexFDO

Authors Yuki Urabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

Publication date 16 December 2020

Full work available at URL https://doi.org/10.4230/LIPIcs.CPM.2018.19

zbMATH Keywords

edit operationLyndon factorizationLyndon treeLyndon word

Mathematics Subject Classification ID

Algorithms on strings (68W32) Analysis of algorithms (68W40)

Recommendations

• Longest substring palindrome after edit
• Computing longest palindromic substring after single-character or block-wise edits
• Longest common substring made fully dynamic
• Faster queries for longest substring palindrome after block edit
• The longest common substring problem
• Longest common factor after one edit operation
• Dynamic and internal longest common substring
• String editing under a combination of constraints
• Longest common substring with approximately \(k\) mismatches

Cites work

• Factorizing words over an ordered alphabet
• Fast Algorithms for Finding Nearest Common Ancestors
• Fast parallel Lyndon factorization with applications
• Faster Lyndon factorization algorithms for SLP and LZ78 compressed text
• Free differential calculus. IV: The quotient groups of the lower central series
• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• Longest common factor after one edit operation
• Lyndon words and short superstrings
• Lyndon words, permutations and trees.
• Minimal non-convex words
• Necklaces of beads in k colors and k-ary de Bruijn sequences
• On Burnside's Problem
• On-line construction of suffix trees
• Parallel RAM algorithms for factorizing words
• Periodic musical sequences and Lyndon words
• Reconstructing a string from its Lyndon arrays
• Simple real-time constant-space string matching
• The ``runs theorem
• The level ancestor problem simplified
• The standard factorization of Lyndon words: an average point of view
• Two-way string-matching

Cited in

(12)

• Minimal unique palindromic substrings after single-character substitution
• The heaviest induced ancestors problem: better data structures and applications
• Shortest unique palindromic substring queries in semi-dynamic settings
• Dynamic and internal longest common substring
• Computing longest palindromic substring after single-character or block-wise edits
• Faster queries for longest substring palindrome after block edit
• Longest substring palindrome after edit
• Data structures for computing unique palindromes in static and non-static strings
• Near-optimal quantum algorithms for string problems
• A textbook solution for dynamic strings
• Shortest cover after edit
• Minimal generators in optimal time

Describes a project that uses

Uses Software

• STAR

This page was built for publication: Longest Lyndon Substring After Edit

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