An efficient algorithm for online square detection

DOI10.1016/j.tcs.2006.06.011zbMath1153.68556OpenAlexW2084844607MaRDI QIDQ860815

Ho-fung Leung, H. F. Ting, Zeshan Peng

Publication date: 9 January 2007

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

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

zbMATH Keywords

online algorithmssquaresstring processingsquare-free detection

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05)

Related Items (2)

A fast algorithm for finding the positions of all squares in a run-length encoded string ⋮ Efficient on-line repetition detection

Uses Software

• TROLL

Cites Work

• An infinite square-free co-CFL
• Applications of an infinite square-free co-CFL
• An optimal algorithm for computing the repetitions in a word
• Optimal off-line detection of repetitions in a string
• Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays
• Efficient parallel algorithms to test square-freeness and factorize strings
• Optimal parallel detection of squares in strings
• Linear time algorithms for finding and representing all the tandem repeats in a string
• Transducers and repetitions
• Classification of noncounting events
• An O(n log n) algorithm for finding all repetitions in a string
• A strongly primitive word of arbitrary length and its application †
• Algorithms on Strings, Trees and Sequences
• An Optimal $O(\log \log N)$-Time Parallel Algorithm for Detecting all Squares in a String
• Simple and flexible detection of contiguous repeats using a suffix tree
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An efficient algorithm for online square detection