Linear-time computation of local periods
Theoretical Computer SciencePublished 24 July 2004
Jean-Pierre Duval, Roman Kolpakov, Grégory Kucherov, Thierry Lecroq, Arnaud Lefebvre
Citations36
SJR quartileQ2
SJR score0.49
SNIP0.94
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
Article dans revue scientifique avec comité de lecture. internationale.
Keywords
Computer Science
Algorithms on strings, trees, and sequences: computer science and computational biology
3,529 Citations1997Dan Gusfield
Cambridge University Press eBooksAlgorithms on Strings, Trees and Sequences
3,045 Citations1997Dan Gusfield
Ukkonen’s method is the method of choice for most problems requiring the construction of a suffix tree, and it will be presented first because it is easier to understand.
SIAM Journal on ComputingFast Pattern Matching in Strings
2,917 Citations1977Donald E. Knuth, James H. Morris +1 more
An algorithm is presented which finds all occurrences of one given string within another, in running time proportional to the sum of the lengths of the strings, showing that the set of concatenations of even palindromes, i.e., the language $\{\alpha \alpha ^R\}^*$, can be recognized in linear time.
Communications of the ACMA fast string searching algorithm
2,292 Citations1977Robert S. Boyer, J Strother Moore
The algorithm has the unusual property that, in most cases, not all of the first i.” in another string, are inspected.
Linear pattern matching algorithms
1,810 Citations1973Peter Weiner
A linear time algorithm for obtaining a compacted version of a bi-tree associated with a given string is presented and indicated how to solve several pattern matching problems, including some from [4] in linear time.
HAL (Le Centre pour la Communication Scientifique Directe)Combinatorics on words
1,751 Citations1984M. Lothaire
Algorithms on strings, trees, and sequences
1,723 Citations1997Dan Gusfield
Cambridge University Press eBooksApplied Combinatorics on Words (Encyclopedia of Mathematics and its Applications)
447 Citations2005M. Lothaire
Binatorics automata and number theory, binatorial mathematics article about binatorial, and algorithms binations of encyclopedia of mathematics.
Finding maximal repetitions in a word in linear time
322 Citations2003Roman Kolpakov, Grégory Kucherov
This work proves a combinatorial result asserting that the sum of exponents of all maximal repetitions of a word of length n is bounded by a linear function in n, which implies that there is only a linear number of maximal repetition in a word.
Combinatorics of Words
319 Citations1997Christian Choffrut, Juhani Karhumäki
This is a survey on combinatorics of words to appear as a chapter in Handbook of Formal Languages about defect effect, equations as properties of words, periodicity, finiteness conditions, avoidabilty and subword complexity.
Information Processing LettersAn optimal algorithm for computing the repetitions in a word
308 Citations1981Maxime Crochemore
This paper presents an algorithm to compute all the repetitions of primitive factors in a word x in time 0( i x i log2 Ix i 9) and proves the optimality of the algorithm is proved by showing that there exist words which have indeed 0( ix I log2 ix i) repetitions, which are Fibonacci words.
Journal of AlgorithmsAn O(n log n) algorithm for finding all repetitions in a string
258 Citations1984Michael G. Main, Richard J. Lorentz
An O(n log n) algorithm is presented to find all repetitions in a string of lenght n, which uses a variation of the Knuth-Morris-Pratt algorithm to finding all partial occurrences of a pattern within a text string.
Journal of the ACMLinear Algorithm for Data Compression via String Matching
227 Citations1981Michael Rodeh, Vaughan Pratt +1 more
A linear implementation of the optimal universal data compression methods of Lempel and Ziv is described and the main tool is McCreight's algorithm for constructing suffix trees.
Journal of Combinatorial Theory Series APeriods in strings
197 Citations1981Leo J. Guibas, Andrew Odlyzko
Journal of Computer and System SciencesLinear time algorithms for finding and representing all the tandem repeats in a string
161 Citations2004Dan Gusfield, Jens Stoye
An O(|S|)-time algorithm that operates on the suffix tree T(S) for a string S, finding and marking the endpoint of every tandem repeat that occurs in S, improves and generalizes several prior efforts to efficiently capture large subsets of tandem repeats.
Journal of the ACMTwo-way string-matching
158 Citations1991Maxime Crochemore, Dominique Perrin
A new string-matching algorithm is presented, which can be viewed as an intermediate between the classical algorithms of Knuth, Morris, and Pratt and Boyer and Moore, which presents the advantage of being remarkably simple which consequently makes its analysis possible.
AlgorithmicaSquares, cubes, and time-space efficient string searching
128 Citations1995Maxime Crochemore, Wojciech Rytter
A cleaner version and a simpler analysis of the GS algorithm that corrects the algorithm given in [GS2] for the computation of periods and presents an optimal parallel algorithm for pattern preprocessing.
Journal of Combinatorial Theory Series AHow Many Squares Can a String Contain?
122 Citations1998Aviezri S. Fraenkel, Jamie Simpson
No position in any word can be the beginning of the rightmost occurrence of more than two squares, from which the maximum number of distinct primitive rooted squares in a word of length n is deduced.
Discrete MathematicsUne caracterisation des mots periodiques
84 Citations1979Roland Assous, Maurice Pouzet
Resumen Le but de cette note est de demontrer le resultat suivant conjecture par R. Fraīsse ∗ : “ Une suite est periodique de periode p si et seulement si p est le plus petie entier k > 0 tel que tout intervalle fini ait un intervalle initial and un intervall final identiques et non vides de longuer au plus egale a k ”.
Theoretical Computer ScienceFinding approximate repetitions under Hamming distance
72 Citations2003Roman Kolpakov, Grégory Kucherov
Journal of AlgorithmsRotations of Periodic Strings and Short Superstrings
67 Citations1997Dany Breslauer, Tao Jiang +1 more
It is proved that for each periodic semiinfinite string ?=a1a2··· of periodq, there exists an integerk, such that for any(finite) string sof periodp, the overlap betweens therotation?k=akak+1··· is at most p+12q, and ifp?q, then the overlapbetweens ?
Finding repeats with fixed gap
44 Citations2002Roman Kolpakov, Grégory Kucherov
The solution uses an algorithm for finding all quasi-squares in two strings, a problem that generalizes the well-known problem of searching for squares.
Theoretical Computer SciencePeriodes et repetitions des mots du monoide libre
35 Citations1979Jean-Pierre Duval
The main result generalizes the theorem of Cesari Vincent according to which the period of a word is the maximum of the minimal repetitions, which allows a sharpened version of the solution to a problem settled by Schutzenberger.
HAL (Le Centre pour la Communication Scientifique Directe)Recherche linéaire d'un carré dans un mot
35 Citations1983Maxime Crochemore
Lecture notes in computer scienceComputation of squares in a string
34 Citations1994S. Rao Kosaraju
A linear time algorithm for computing a square substring from each position of a given string over a finite alphabet using suffix trees for strings is designed.
Journal of Combinatorial Theory Series ACombinatorics of periods in strings
33 Citations2003Éric Rivals, Sven Rahmann
Lecture notes in computer scienceA periodicity theorem on words and applications
20 Citations1995Filippo Mignosi, Antonio Restivo +1 more
It is proved that a periodicity theorem on words that has strong analogies with the Critical Factorization theorem and three applications of it are shown.
Lecture notes in computer scienceOn the Complexity of Determining the Period of a String
12 Citations2000Artur Czumaj, Leszek Gçasieniec
A deterministic algorithm that computes the period of a string using m+O(m3/4) comparisons is presented, which is the first algorithm that have the worstcase complexity m + o(m).
Theoretical Computer ScienceRecurrence and periodicity in infinite words from local periods
10 Citations2001J.-P. Duval, Filippo Mignosi +1 more
This work gives a characterization of recurrent, periodic and eventually periodic infinite words in terms of local periods by using local conditions for recurrence and periodicity in infinite words.
BRICS Report SeriesRotation of Periodic Strings and Short Superstrings
9 Citations1996Dany Breslauer, Tao Jiang +1 more
Theoretical Computer SciencePériodes locales et propagation de périodes dans un mot
9 Citations1998Jean-Pierre Duval