Efficient parallel algorithms to test square-freeness and factorize strings

DOI10.1016/0020-0190(91)90223-5zbMath0736.68033OpenAlexW1990387309MaRDI QIDQ1178198

Wojciech Rytter, Maxime Crochemore

Publication date: 26 June 1992

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(91)90223-5

zbMATH Keywords

CRCW PRAM

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Distributed algorithms (68W15) Computing methodologies for text processing; mathematical typography (68U15)

Related Items (8)

P-complete problems in data compression ⋮ An efficient algorithm for online square detection ⋮ Bounded size dictionary compression: SC\(^{k}\)-completeness and NC algorithms. ⋮ Efficient string matching on packed texts ⋮ Lempel-Ziv data compression on parallel and distributed systems ⋮ Parallelism and dictionary based data compression ⋮ Optimal parallel algorithms for periods, palindromes and squares ⋮ Detecting regularities on grammar-compressed strings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Transducers and repetitions
• An O(n log n) algorithm for finding all repetitions in a string
• An O(logn) parallel connectivity algorithm
• A universal algorithm for sequential data compression

This page was built for publication: Efficient parallel algorithms to test square-freeness and factorize strings