Optimal parallel detection of squares in strings

DOI10.1007/BF01758848zbMath0748.68022MaRDI QIDQ1194333

Alberto Apostolico

Publication date: 27 September 1992

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

string matchingcombinatorial algorithms on wordsavoidable regularitiessquares and repetitions in a string

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15) Distributed algorithms (68W15)

Related Items (7)

An efficient algorithm for online square detection ⋮ Efficient string matching on packed texts ⋮ String-matching on ordered alphabets ⋮ Efficient detection of quasiperiodicities in strings ⋮ Efficient CRCW-PRAM algorithms for universal substring searching ⋮ Optimal parallel algorithms for periods, palindromes and squares ⋮ Optimal discovery of repetitions in 2D

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The equation \(a_ M=b^ Nc^ P\) in a free group
• Structural properties of the string statistics problem
• Parallel construction of a suffix tree with applications
• 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
• Factorizing words over an ordered alphabet
• An O(n log n) algorithm for finding all repetitions in a string
• Efficient Parallel Algorithms for String Editing and Related Problems
• Relations between Concurrent-Write Models of Parallel Computation
• Bounds for the String Editing Problem
• Free differential calculus. IV: The quotient groups of the lower central series

This page was built for publication: Optimal parallel detection of squares in strings