Extracting powers and periods in a word from its runs structure

DOI10.1016/j.tcs.2013.11.018zbMath1295.68174OpenAlexW2051593658WikidataQ61677846 ScholiaQ61677846MaRDI QIDQ389938

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

Publication date: 22 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.11.018

zbMATH Keywords

local periodpowers of a wordprimitive wordrun in a word

Mathematics Subject Classification ID

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

Related Items

Prefix frequency of lost positions, Efficiently computing runs on a trie, Improved upper bounds on all maximal \(\alpha\)-gapped repeats and palindromes, Upper bounds on distinct maximal (sub-)repetitions in compressed strings, Computing minimal and maximal suffixes of a substring, Closed factorization, Maximum number of distinct and nonequivalent nonstandard squares in a word, Multidimensional period recovery, Lower bounds for the number of repetitions in 2D strings, Longest previous overlapping factor array, Searching of gapped repeats and subrepetitions in a word, Constructing Words with High Distinct Square Densities, The square density of words having a sequence of FS-double squares, The “Runs” Theorem, Unnamed Item, Tight Upper Bounds on Distinct Maximal (Sub-)Repetitions in Highly Compressible Strings, Period recovery of strings over the Hamming and edit distances, On the number of gapped repeats with arbitrary gap, Fast algorithm for partial covers in words, Detecting One-Variable Patterns, Shortest covers of all cyclic shifts of a string, Internal dictionary matching, Some results on the number of periodic factors in words, Repetition Detection in a Dynamic String, Two-dimensional maximal repetitions, Efficient representation and counting of antipower factors in words, Computing runs on a trie, Quasi-Linear-Time Algorithm for Longest Common Circular Factor, Efficient Ranking of Lyndon Words and Decoding Lexicographically Minimal de Bruijn Sequence, Efficient enumeration of non-equivalent squares in partial words with few holes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• New simple efficient algorithms computing powers and runs in strings
• The ``runs conjecture
• Linear-time computation of local periods
• Repetitions in strings: algorithms and combinatorics
• How many squares can a string contain?
• Linear time algorithms for finding and representing all the tandem repeats in a string
• Detecting leftmost maximal periodicities
• A note on the number of squares in a word
• A simple proof that a word of length \(n\) has at most \(2n\) distinct squares
• Fast Algorithms for Finding Nearest Common Ancestors
• Efficient Algorithms for Two Extensions of LPF Table: The Power of Suffix Arrays
• Fast and Practical Algorithms for Computing All the Runs in a String
• Position-Restricted Substring Searching
• Space Efficient Linear Time Construction of Suffix Arrays
• A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array
• On the Maximal Number of Cubic Subwords in a String
• Jewels of Stringology
• Orthogonal range searching on the RAM, revisited
• Algorithms on Strings