New simple efficient algorithms computing powers and runs in strings

DOI10.1016/J.DAM.2013.05.009MaRDI QIDQ496538zbMATH OpenOpenAlexDBLPWikidataFDO

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

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)

Recommendations

• Fast and Practical Algorithms for Computing All the Runs in a String
• Extracting powers and periods in a word from its runs structure
• scientific article; zbMATH DE number 4078831
• Maximal repetitions in strings
• Computing runs on a general alphabet

Cites work

• Algorithms on Strings
• An O(n log n) algorithm for finding all repetitions in a string
• An optimal algorithm for computing the repetitions in a word
• Bounds on Powers in Strings
• Combinatorial Pattern Matching
• Computing and Combinatorics
• Efficient Algorithms for Two Extensions of LPF Table: The Power of Suffix Arrays
• How many squares can a string contain?
• scientific article; zbMATH DE number 3898807 (Why is no real title available?)
• scientific article; zbMATH DE number 3913712 (Why is no real title available?)
• scientific article; zbMATH DE number 3976360 (Why is no real title available?)
• Jewels of Stringology
• Linear time algorithms for finding and representing all the tandem repeats in a string
• Mathematical Foundations of Computer Science 2005
• New simple efficient algorithms computing powers and runs in strings
• On the maximal number of cubic runs in a string
• Optimal off-line detection of repetitions in a string
• Repetitions in strings: algorithms and combinatorics
• Simple and flexible detection of contiguous repeats using a suffix tree
• Transducers and repetitions
• Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays

Cited in

(9)

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

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

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