Fast, practical algorithms for computing all the repeats in a string

DOI10.1007/S11786-010-0033-6MaRDI QIDQ626893zbMATH OpenOpenAlexFDO

Authors Simon J. Puglisi, W. F. Smyth, Munina Yusufu

Publication date 19 February 2011

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

Full work available at URL http://hdl.handle.net/20.500.11937/36774

zbMATH Keywords

suffix treesuffix arrayrepetitionrepeat

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Nonnumerical algorithms (68W05) Combinatorics on words (68R15) Algorithms on strings (68W32)

Recommendations

• Fast and Practical Algorithms for Computing All the Runs in a String
• scientific article; zbMATH DE number 2105037
• Efficient repeat finding in sets of strings via suffix arrays
• Faster algorithms for computing maximal multirepeats in multiple sequences
• An O(n log n) algorithm for finding all repetitions in a string

Cites work

• scientific article; zbMATH DE number 2038766 (Why is no real title available?)
• scientific article; zbMATH DE number 1786458 (Why is no real title available?)
• scientific article; zbMATH DE number 2105037 (Why is no real title available?)
• Algorithm Theory - SWAT 2004
• Algorithms on Strings, Trees and Sequences
• Efficient Computation of Substring Equivalence Classes with Suffix Arrays
• Engineering a lightweight suffix array construction algorithm
• Fast, practical algorithms for computing all the repeats in a string
• New approaches for computer analysis of nucleic acid sequences.
• Replacing suffix trees with enhanced suffix arrays
• Space efficient linear time construction of suffix arrays
• Space-Time Tradeoffs for Longest-Common-Prefix Array Computation

Cited in

(14)

• New complexity results for the \(k\)-covers problem
• On context-diverse repeats and their incremental computation
• Efficient repeat finding in sets of strings via suffix arrays
• scientific article; zbMATH DE number 2105041 (Why is no real title available?)
• Computing regularities in strings: a survey
• String covering with optimal covers
• Simple and flexible detection of contiguous repeats using a suffix tree
• Faster algorithms for computing maximal multirepeats in multiple sequences
• Fast algorithm for Vernier search of long repeats in DNA sequences with bounded error density
• scientific article; zbMATH DE number 2105037 (Why is no real title available?)
• Fast algorithms for finding a minimum repetition representation of strings and trees
• Alphabet-independent algorithms for finding context-sensitive repeats in linear time
• Fast, practical algorithms for computing all the repeats in a string
• Efficient computation of substring equivalence classes with suffix arrays

This page was built for publication: Fast, practical algorithms for computing all the repeats in a string

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