An O(n log n) algorithm for finding all repetitions in a string
From MaRDI portal
Publication:3339319
DOI10.1016/0196-6774(84)90021-XzbMath0547.68083OpenAlexW1973456884WikidataQ64357146 ScholiaQ64357146MaRDI QIDQ3339319
Michael G. Main, Richard J. Lorentz
Publication date: 1984
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(84)90021-x
Related Items
Algorithms For Computing Approximate Repetitions In Musical Sequences, Structural properties of the string statistics problem, New bounds and extended relations between prefix arrays, border arrays, undirected graphs, and indeterminate strings, Speeding up the detection of evolutive tandem repeats, Longest common extensions in trees, Order-preserving indexing, Parallel two dimensional witness computation, A fast algorithm for finding the positions of all squares in a run-length encoded string, More results on overlapping squares, Time-Space Trade-Offs for Longest Common Extensions, ASYMPTOTIC BEHAVIOUR OF THE MAXIMAL NUMBER OF SQUARES IN STANDARD STURMIAN WORDS, The number of runs in a string, Long unavoidable patterns, Computing longest common extensions in partial words, An efficient algorithm for online square detection, Succinct 2D dictionary matching, Avoidable patterns on two letters, Distinct squares in run-length encoded strings, Locating maximal approximate runs in a string, Longest Common Extensions in Trees, Longest Common Extensions in Sublinear Space, Computing primitively-rooted squares and runs in partial words, Longest common extension, Fast and Simple Computations Using Prefix Tables Under Hamming and Edit Distance, Computing Primitively-Rooted Squares and Runs in Partial Words, A characterization of the squares in a Fibonacci string, The longest common extension problem revisited and applications to approximate string searching, Constructing Words with High Distinct Square Densities, Efficient learning of real time one-counter automata, Large-scale detection of repetitions, On shuffled-square-free words, Towards a Solution to the “Runs” Conjecture, Inplace run-length 2d compressed search., Finding approximate repetitions under Hamming distance., The three squares lemma revisited, The “Runs” Theorem, Near-optimal quantum algorithms for string problems, Most pseudo-copy languages are not context-free, Speeding up the detection of tandem repeats over the edit distance, Double string tandem repeats, Crochemore's partitioning on weighted strings and applications, Efficient string matching on packed texts, Time-space trade-offs for longest common extensions, An efficient algorithm to test square-freeness of strings compressed by straight-line programs, Bounds on Powers in Strings, Fast algorithms for finding a minimum repetition representation of strings and trees, WORD COMPLEXITY AND REPETITIONS IN WORDS, Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays, Efficient parallel algorithms to test square-freeness and factorize strings, Optimal parallel algorithms for Prefix Matching, Efficient Computation of 2-Covers of a String., Indeterminate strings, prefix arrays \& undirected graphs, New simple efficient algorithms computing powers and runs in strings, Fast parallel string prefix-matching, A prefix array for parameterized strings, Optimal parallel detection of squares in strings, Efficient on-line repetition detection, Efficient detection of quasiperiodicities in strings, Efficient counting of square substrings in a tree, Finding similar consensus between trees: An algorithm and a distance hierarchy, Computing regularities in strings: a survey, On the maximum number of cubic subwords in a word, Linear time algorithms for finding and representing all the tandem repeats in a string, The ``runs conjecture, New complexity results for the \(k\)-covers problem, Linear-time computation of local periods, NUMBER OF OCCURRENCES OF POWERS IN STRINGS, Identifying consensus of trees through alignment, Space efficient search for maximal repetitions, Optimal bounds for computing \({\alpha}\)-gapped repeats, Fast parallel and serial multidimensional approximate array matching, Approximate periods of strings, Simple and flexible detection of contiguous repeats using a suffix tree, Optimal parallel algorithms for periods, palindromes and squares, Detecting regularities on grammar-compressed strings, Repetition Detection in a Dynamic String, Fibonacci arrays and their two-dimensional repetitions, Detecting leftmost maximal periodicities, Repetitions in strings: algorithms and combinatorics, Repetitive perhaps, but certainly not boring, Optimal discovery of repetitions in 2D, Squares and primitivity in partial words, ONLINE AND DYNAMIC RECOGNITION OF SQUAREFREE STRINGS, Approximate periodicity, Inferring an indeterminate string from a prefix graph, Optimal Parallel Searching an Array for Certain Repetitions, Repetitions detection on a linear array with reconfigurable pipelined bus system, Almost linear time computation of maximal repetitions in run length encoded strings, Efficient enumeration of non-equivalent squares in partial words with few holes, Three overlapping squares: the general case characterized \& applications
