Computing regularities in strings: a survey
From MaRDI portal
Publication:1761494
DOI10.1016/j.ejc.2012.07.010zbMath1253.68277OpenAlexW1969885991MaRDI QIDQ1761494
Publication date: 15 November 2012
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ejc.2012.07.010
Related Items
Prefix frequency of lost positions, The number of runs in a string, Enhanced string covering, String rearrangement inequalities and a total order between primitive words, String Covering: A Survey, The “Runs” Theorem, A simple yet time-optimal and linear-space algorithm for shortest unique substring queries, Partial words with a unique position starting a square, Fast computation of abelian runs, The wide window string matching algorithm, Combinatorics on partial word correlations, On approximate enhanced covers under Hamming distance, Repetitions in strings: algorithms and combinatorics
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The three squares lemma revisited
- Algorithms for computing abelian periods of words
- New complexity results for the \(k\)-covers problem
- Fast, practical algorithms for computing all the repeats in a string
- Efficient detection of quasiperiodicities in strings
- A new approach to the periodicity lemma on strings with holes
- Optimal superprimitivity testing for strings
- Replacing suffix trees with enhanced suffix arrays
- Maximal repetitions in strings
- How many runs can a string contain?
- A new approach to pattern matching in degenerate DNA/RNA sequences and distributed pattern matching
- Lempel-Ziv factorization using less time \& space
- Computing longest previous factor in linear time and applications
- Optimality of some algorithms to detect quasiperiodicities
- Intersecting periodic words
- An optimal algorithm for computing the repetitions in a word
- Optimal off-line detection of repetitions in a string
- An on-line string superprimitivity test
- Partial words and a theorem of Fine and Wilf
- An optimal algorithm to compute all the covers of a string
- Repetitive perhaps, but certainly not boring
- Detecting leftmost maximal periodicities
- Squares, cubes, and time-space efficient string searching
- On-line construction of suffix trees
- Covering a string
- More results on overlapping squares
- Computing the \(\lambda \)-covers of a string
- Pattern Matching in Compressed Texts and Images
- A comparison of index-based lempel-Ziv LZ77 factorization algorithms
- Efficient Seeds Computation Revisited
- On the Right-Seed Array of a String
- Minimum Unique Substrings and Maximum Repeats
- Suffix Arrays: A New Method for On-Line String Searches
- An O(n log n) algorithm for finding all repetitions in a string
- Faster Algorithms for Computing Maximal Multirepeats in Multiple Sequences
- Fast and Practical Algorithms for Computing All the Runs in a String
- Efficient Computation of Substring Equivalence Classes with Suffix Arrays
- Towards a Solution to the “Runs” Conjecture
- Not So Many Runs in Strings
- An Online Algorithm for Finding the Longest Previous Factors
- Linear-Time Construction of Suffix Arrays
- Space Efficient Linear Time Construction of Suffix Arrays
- Space-Time Tradeoffs for Longest-Common-Prefix Array Computation
- Linear Time Suffix Array Construction Using D-Critical Substrings
- Permuted Longest-Common-Prefix Array
- LPF Computation Revisited
- A Space-Economical Suffix Tree Construction Algorithm
- On the Complexity of Finite Sequences
- Fast Pattern Matching in Strings
- A universal algorithm for sequential data compression
- Algorithms on Strings, Trees and Sequences
- A Linear-Time Algorithm for Seeds Computation
- Algorithmic Combinatorics on Partial Words
- Algorithm Theory - SWAT 2004
- Uniqueness Theorems for Periodic Functions
- Computing the λ-Seeds of a String
- The Number of Runs in a String: Improved Analysis of the Linear Upper Bound
- A FIRST APPROACH TO FINDING COMMON MOTIFS WITH GAPS
- A New Periodicity Lemma
- Computing the cover array in linear time
