New simple efficient algorithms computing powers and runs in strings

DOI10.1016/j.dam.2013.05.009zbMath1329.68310DBLPjournals/dam/CrochemoreIKRRSW14OpenAlexW2008405278WikidataQ61677849 ScholiaQ61677849MaRDI QIDQ496538

Krzysztof Stencel, Costas S. Iliopoulos, Wojciech Rytter, Maxime Crochemore, Jakub Radoszewski, Tomasz Walen, Marcin Kubica

Publication date: 22 September 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2013.05.009

zbMATH Keywords

cube in a stringdictionary of basic factorsrun in a stringsquare in a string

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algorithms on strings (68W32)

Related Items (7)

Locating maximal approximate runs in a string ⋮ Extracting powers and periods in a word from its runs structure ⋮ Property Suffix Array with Applications in Indexing Weighted Sequences ⋮ New simple efficient algorithms computing powers and runs in strings ⋮ Efficient counting of square substrings in a tree ⋮ Optimal bounds for computing \({\alpha}\)-gapped repeats ⋮ On primary and secondary repetitions in words

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• New simple efficient algorithms computing powers and runs in strings
• Repetitions in strings: algorithms and combinatorics
• An optimal algorithm for computing the repetitions in a word
• Optimal off-line detection of repetitions in a string
• Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays
• How many squares can a string contain?
• Linear time algorithms for finding and representing all the tandem repeats in a string
• Transducers and repetitions
• An O(n log n) algorithm for finding all repetitions in a string
• Efficient Algorithms for Two Extensions of LPF Table: The Power of Suffix Arrays
• Bounds on Powers in Strings
• On the Maximal Number of Cubic Runs in a String
• Jewels of Stringology
• Computing and Combinatorics
• Algorithms on Strings
• Mathematical Foundations of Computer Science 2005
• Combinatorial Pattern Matching
• Simple and flexible detection of contiguous repeats using a suffix tree

This page was built for publication: New simple efficient algorithms computing powers and runs in strings