A Faster Algorithm for Computing Maximal $$\alpha $$-gapped Repeats in a String

DOI10.1007/978-3-319-23826-5_13zbMath1433.68636OpenAlexW2228639851MaRDI QIDQ2949836

Yuka Tanimura, Yuta Fujishige, Shunsuke Inenaga, Masayuki Takeda, Hideo Bannai, Tomohiro I.

Publication date: 2 October 2015

Published in: String Processing and Information Retrieval (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-23826-5_13

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Related Items (6)

Factorizing strings into repetitions ⋮ Tighter bounds and optimal algorithms for all maximal \(\alpha\)-gapped repeats and palindromes. Finding all maximal \(\alpha\)-gapped repeats and palindromes in optimal worst case time on integer alphabets ⋮ On the number of gapped repeats with arbitrary gap ⋮ Optimal bounds for computing \({\alpha}\)-gapped repeats ⋮ Counting maximal-exponent factors in words ⋮ Efficient representation and counting of antipower factors in words

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear-time algorithm for a special case of disjoint set union
• The smallest automaton recognizing the subwords of a text
• Linear time algorithms for finding and representing all the tandem repeats in a string
• Transducers and repetitions
• On-line construction of suffix trees
• Suffix Arrays: A New Method for On-Line String Searches
• A universal algorithm for sequential data compression
• Algorithms on Strings, Trees and Sequences
• Searching of Gapped Repeats and Subrepetitions in a Word

This page was built for publication: A Faster Algorithm for Computing Maximal $$\alpha $$-gapped Repeats in a String