Fast and Practical Algorithms for Computing All the Runs in a String

DOI10.1007/978-3-540-73437-6_31zbMath1138.68658OpenAlexW1593730394MaRDI QIDQ3506932

W. F. Smyth, Gang Chen, Simon J. Puglisi

Publication date: 17 June 2008

Published in: Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-73437-6_31

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Combinatorics on words (68R15)

Related Items (16)

More results on overlapping squares ⋮ Extracting powers and periods in a word from its runs structure ⋮ The three squares lemma revisited ⋮ The “Runs” Theorem ⋮ A \textit{really} simple approximation of smallest grammar ⋮ Speeding up the detection of tandem repeats over the edit distance ⋮ Faster semi-external suffix sorting ⋮ Ostrowski-automatic sequences: theory and applications ⋮ An Online Algorithm for Finding the Longest Previous Factors ⋮ Efficient on-line repetition detection ⋮ Computing longest previous factor in linear time and applications ⋮ Computing regularities in strings: a survey ⋮ New complexity results for the \(k\)-covers problem ⋮ Repetitions in strings: algorithms and combinatorics ⋮ Faster online computation of the succinct longest previous factor array ⋮ Three overlapping squares: the general case characterized \& applications

This page was built for publication: Fast and Practical Algorithms for Computing All the Runs in a String