Efficient on-line repetition detection

DOI10.1016/j.tcs.2008.08.038zbMath1153.68043OpenAlexW1996278676MaRDI QIDQ955034

Gen-Huey Chen, Jin-Ju Hong

Publication date: 18 November 2008

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.08.038

zbMATH Keywords

squarerepetitionon-line detection

Mathematics Subject Classification ID

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

Related Items (2)

Online Detection of Repetitions with Backtracking ⋮ Computing runs on a general alphabet

Cites Work

• An efficient algorithm for online square detection
• Computing longest previous factor in linear time and applications
• An optimal algorithm for computing the repetitions in a word
• Optimal off-line detection of repetitions in a string
• String matching in Lempel-Ziv compressed strings
• Linear time algorithms for finding and representing all the tandem repeats in a string
• Transducers and repetitions
• Squares, cubes, and time-space efficient string searching
• On-line construction of suffix trees
• An O(n log n) algorithm for finding all repetitions in a string
• Fast and Practical Algorithms for Computing All the Runs in a String
• Fast Pattern Matching in Strings
• Algorithms on Strings, Trees and Sequences
• Uniqueness Theorems for Periodic Functions
• Simple and flexible detection of contiguous repeats using a suffix tree
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Efficient on-line repetition detection