Simple and flexible detection of contiguous repeats using a suffix tree

DOI10.1016/S0304-3975(01)00121-9MaRDI QIDQ5958334zbMATH OpenOpenAlexWikidataFDO

Authors Jens Stoye, Dan Gusfield

Publication date 3 March 2002

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(01)00121-9

zbMATH Keywords

repeatssequence analysissuffix treetandem arraystandem repeats

Mathematics Subject Classification ID

Searching and sorting (68P10)

Recommendations

• Linear time algorithms for finding and representing all the tandem repeats in a string
• scientific article; zbMATH DE number 2105037
• Efficient repeat finding in sets of strings via suffix arrays
• A linear algorithm for the detection of evolutive tandem repeats
• Fast, practical algorithms for computing all the repeats in a string

Cites work

• A characterization of the squares in a Fibonacci string
• A Space-Economical Suffix Tree Construction Algorithm
• Algorithms on Strings, Trees and Sequences
• An O(n log n) algorithm for finding all repetitions in a string
• An optimal algorithm for computing the repetitions in a word
• How many squares can a string contain?
• How many squares must a binary sequence contain?
• scientific article; zbMATH DE number 3913711 (Why is no real title available?)
• scientific article; zbMATH DE number 3913712 (Why is no real title available?)
• scientific article; zbMATH DE number 801745 (Why is no real title available?)
• scientific article; zbMATH DE number 826052 (Why is no real title available?)
• scientific article; zbMATH DE number 1390079 (Why is no real title available?)
• Linear time algorithms for finding and representing all the tandem repeats in a string
• On-line construction of suffix trees
• Optimal off-line detection of repetitions in a string
• Squares, cubes, and time-space efficient string searching
• Suffix Arrays: A New Method for On-Line String Searches
• The exact number of squares in Fibonacci words

Cited in

(21)

• Discovering subword associations in strings in time linear in the output size
• Repetitive perhaps, but certainly not boring
• String cadences
• Linear time algorithms for finding and representing all the tandem repeats in a string
• Finding patterns and periods in Cartesian tree matching
• Fast algorithms for finding a minimum repetition representation of strings and trees
• Optimal discovery of repetitions in 2D
• Most pseudo-copy languages are not context-free
• Double string tandem repeats
• Order-preserving indexing
• scientific article; zbMATH DE number 2105037 (Why is no real title available?)
• On a lemma of Crochemore and Rytter
• New simple efficient algorithms computing powers and runs in strings
• A linear algorithm for the detection of evolutive tandem repeats
• A sublinear time string prefix square detection algorithm
• scientific article; zbMATH DE number 7651094 (Why is no real title available?)
• The number of repetitions in 2D-strings
• Counting distinct square substrings in sublinear time
• A fast algorithm for finding the positions of all squares in a run-length encoded string
• An efficient algorithm for online square detection
• Efficient on-line repetition detection

Describes a project that uses

Uses Software

• REPuter

This page was built for publication: Simple and flexible detection of contiguous repeats using a suffix tree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5958334)