An optimal algorithm for computing the repetitions in a word
From MaRDI portal
Publication:1155963
DOI10.1016/0020-0190(81)90024-7zbMath0467.68075DBLPjournals/ipl/Crochemore81OpenAlexW2067787802WikidataQ61677999 ScholiaQ61677999MaRDI QIDQ1155963
Publication date: 1981
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(81)90024-7
partitioningoptimalityanalysis of algorithmFibonacci wordssquarefreenesspowerfreenessrepetition in words
Free semigroups, generators and relations, word problems (20M05) Artificial intelligence (68T99) Semigroups in automata theory, linguistics, etc. (20M35) Discrete mathematics in relation to computer science (68R99)
Related Items (only showing first 100 items - show all)
Algorithms For Computing Approximate Repetitions In Musical Sequences ⋮ Structural properties of the string statistics problem ⋮ An optimal algorithm to compute all the covers of a string ⋮ A linear time lower bound on McCreight and general updating algorithms for suffix trees ⋮ Improved linear systolic algorithms for substring statistics ⋮ Speeding up the detection of evolutive tandem repeats ⋮ A coarse-grained multicomputer algorithm for the detection of repetitions ⋮ A fast algorithm for finding the positions of all squares in a run-length encoded string ⋮ A note on the number of squares in a word ⋮ More results on overlapping squares ⋮ On left and right seeds of a string ⋮ Multidimensional period recovery ⋮ ASYMPTOTIC BEHAVIOUR OF THE MAXIMAL NUMBER OF SQUARES IN STANDARD STURMIAN WORDS ⋮ On the approximation ratio of LZ-end to LZ77 ⋮ The number of runs in a string ⋮ Detecting morphic images of a word: On the rank of a pattern ⋮ Computing the \(\lambda \)-covers of a string ⋮ An efficient algorithm for online square detection ⋮ ZIV-LEMPEL AND CROCHEMORE FACTORIZATIONS OF THE GENERALIZED PERIOD-DOUBLING WORD ⋮ Unnamed Item ⋮ Locating maximal approximate runs in a string ⋮ Covering a string ⋮ Computing primitively-rooted squares and runs in partial words ⋮ Searching of gapped repeats and subrepetitions in a word ⋮ Computing Primitively-Rooted Squares and Runs in Partial Words ⋮ Efficient solving of the word equations in one variable ⋮ Longest $$\alpha $$-Gapped Repeat and Palindrome ⋮ A characterization of the squares in a Fibonacci string ⋮ On Prefix/Suffix-Square Free Words ⋮ Constructing Words with High Distinct Square Densities ⋮ On shuffled-square-free words ⋮ Towards a Solution to the “Runs” Conjecture ⋮ Weak repetitions in Sturmian strings. ⋮ Generalizations of suffix arrays to multi-dimensional matrices. ⋮ Finding approximate repetitions under Hamming distance. ⋮ The three squares lemma revisited ⋮ String Covering: A Survey ⋮ Computing all subtree repeats in ordered trees ⋮ Unnamed Item ⋮ Period recovery of strings over the Hamming and edit distances ⋮ Polynomial time multiplication and normal forms in free bands ⋮ On the number of gapped repeats with arbitrary gap ⋮ Decision Algorithms for Fibonacci-Automatic Words, III: Enumeration and Abelian Properties ⋮ Crochemore's partitioning on weighted strings and applications ⋮ Efficient string matching on packed texts ⋮ Un réseau linéaire pour la reconnaissance des mots sans carré ⋮ Bounds on Powers in Strings ⋮ Detecting the morphic images of a word : improving the general algorithm ⋮ Closest periodic vectors in \(L_p\) spaces ⋮ Optimal off-line detection of repetitions in a string ⋮ Experimental evaluation of algorithms for computing quasiperiods ⋮ Maximal repetitions in strings ⋮ 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 ⋮ How many runs can a string contain? ⋮ Efficient Computation of 2-Covers of a String. ⋮ \(k\)-abelian pattern matching ⋮ New simple efficient algorithms computing powers and runs in strings ⋮ Average number of occurrences of repetitions in a necklace ⋮ Polynomial-Time Approximation Algorithms for Weighted LCS Problem ⋮ Optimal parallel detection of squares in strings ⋮ Efficient on-line repetition detection ⋮ Efficient detection of quasiperiodicities in strings ⋮ 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 ⋮ New complexity results for the \(k\)-covers problem ⋮ Linear-time computation of local periods ⋮ NUMBER OF OCCURRENCES OF POWERS IN STRINGS ⋮ Optimal bounds for computing \({\alpha}\)-gapped repeats ⋮ Optimality of some algorithms to detect quasiperiodicities ⋮ On the number of frames in binary words ⋮ Approximate periods of strings ⋮ Simple and flexible detection of contiguous repeats using a suffix tree ⋮ Generalized approximate regularities in strings ⋮ Optimal parallel algorithms for periods, palindromes and squares ⋮ Repetition Detection in a Dynamic String ⋮ On the Prefix–Suffix Duplication Reduction ⋮ How many squares can a string contain? ⋮ On primary and secondary repetitions in words ⋮ Fibonacci arrays and their two-dimensional repetitions ⋮ Detecting leftmost maximal periodicities ⋮ Repetitions in strings: algorithms and combinatorics ⋮ Generalizations of suffix arrays to multi-dimensional matrices. ⋮ AVERAGE VALUE OF SUM OF EXPONENTS OF RUNS IN A STRING ⋮ The exact number of squares in Fibonacci words ⋮ Quasiperiodicity and string covering ⋮ Repetitions in Sturmian strings ⋮ Repetitive perhaps, but certainly not boring ⋮ Constructing suffix arrays in linear time ⋮ Optimal discovery of repetitions in 2D ⋮ Squares and primitivity in partial words ⋮ ONLINE AND DYNAMIC RECOGNITION OF SQUAREFREE STRINGS ⋮ Approximate periodicity ⋮ Optimal Parallel Searching an Array for Certain Repetitions ⋮ Repetitions detection on a linear array with reconfigurable pipelined bus system ⋮ Sequences generated by infinitely iterated morphisms ⋮ Three overlapping squares: the general case characterized \& applications ⋮ Near-optimal quantum algorithms for string problems
Cites Work
This page was built for publication: An optimal algorithm for computing the repetitions in a word
