Linear time algorithms for finding and representing all the tandem repeats in a string

DOI10.1016/j.jcss.2004.03.004zbMath1076.68111OpenAlexW1967382114MaRDI QIDQ1765295

Publication date: 23 February 2005

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://pub.uni-bielefeld.de/record/1773569

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Combinatorics on words (68R15)

Related Items

Tandem Duplications, Segmental Duplications and Deletions, and Their Applications ⋮ Speeding up the detection of evolutive tandem repeats ⋮ Longest common extensions in trees ⋮ Order-preserving indexing ⋮ 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 ⋮ Time-Space Trade-Offs for Longest Common Extensions ⋮ Computing suffix links for suffix trees and arrays ⋮ Maximum number of distinct and nonequivalent nonstandard squares in a word ⋮ Multidimensional period recovery ⋮ Computing longest common extensions in partial words ⋮ An efficient algorithm for online square detection ⋮ Replacing suffix trees with enhanced suffix arrays ⋮ 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 ⋮ Longest common extension ⋮ Searching of gapped repeats and subrepetitions in a word ⋮ Extracting powers and periods in a word from its runs structure ⋮ A Faster Algorithm for Computing Maximal $$\alpha $$-gapped Repeats in a String ⋮ The longest common extension problem revisited and applications to approximate string searching ⋮ Constructing Words with High Distinct Square Densities ⋮ The square density of words having a sequence of FS-double squares ⋮ Two-dimensional Fibonacci words: tandem repeats and factor complexity ⋮ Finding approximate repetitions under Hamming distance. ⋮ Unnamed Item ⋮ Sensitivity of string compressors and repetitiveness measures ⋮ Period recovery of strings over the Hamming and edit distances ⋮ Mining approximate patterns with frequent locally optimal occurrences ⋮ Unnamed Item ⋮ On the number of gapped repeats with arbitrary gap ⋮ Time-space trade-offs for longest common extensions ⋮ Fast algorithms for finding a minimum repetition representation of strings and trees ⋮ Fast algorithm for partial covers in words ⋮ New simple efficient algorithms computing powers and runs in strings ⋮ Lempel-Ziv Factorization Revisited ⋮ Efficient on-line repetition detection ⋮ Efficient counting of square substrings in a tree ⋮ Computing longest previous factor in linear time and applications ⋮ Shortest covers of all cyclic shifts of a string ⋮ Forty Years of Text Indexing ⋮ Linear-time computation of local periods ⋮ On suffix extensions in suffix trees ⋮ Lempel-Ziv factorization powered by space efficient suffix trees ⋮ Simple and flexible detection of contiguous repeats using a suffix tree ⋮ On the tiling by translation problem ⋮ Repetition Detection in a Dynamic String ⋮ Two-dimensional maximal repetitions ⋮ Efficient representation and counting of antipower factors in words ⋮ Repetitions in strings: algorithms and combinatorics ⋮ Small-space LCE data structure with constant-time queries ⋮ Computing the Tandem Duplication Distance is NP-Hard ⋮ Lazy Lempel-Ziv Factorization Algorithms ⋮ Efficient enumeration of non-equivalent squares in partial words with few holes

Cites Work