Linear time runs over general ordered alphabets

DOI10.4230/LIPICS.ICALP.2021.63MaRDI QIDQ7241161zbMATH OpenFDO

Authors Jonas Ellert, Johannes Fischer

Publication date 12 May 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2021.63

zbMATH Keywords

combinatorics on wordsgeneral ordered alphabetslongest common extensionLyndon arrayrunssquaresstring algorithms

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A Series of Run-Rich Strings
• An O(n log n) algorithm for finding all repetitions in a string
• Computing runs on a general alphabet
• Computing runs on a trie
• Extracting powers and periods in a word from its runs structure
• Faster longest common extension queries in strings over general alphabets
• Finding maximal repetitions in a word in linear time
• How many runs can a string contain?
• Lempel-Ziv factorization may be harder than computing all runs
• Maximal repetitions in strings
• Near-optimal computation of runs over general alphabet via non-crossing LCE queries
• Prefix frequency of lost positions
• Repetitions in strings: algorithms and combinatorics
• Sorting in linear time?
• Space efficient construction of Lyndon arrays in linear time
• The ``runs conjecture
• The ``runs theorem
• The equation \(a_ M=b^ Nc^ P\) in a free group
• The Number of Runs in a String: Improved Analysis of the Linear Upper Bound
• Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE

Cited in

(3)

• Minimal generators in optimal time
• Counting distinct square substrings in sublinear time
• Fast computation of k-runs, parameterized squares, and other generalised squares

This page was built for publication: Linear time runs over general ordered alphabets

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